GA-based Task Allocation by Throughput Prediction

概要

論文の詳細を見る
Recently, multimedia data processing dealing with audio and visual data and various combinations of such data is gaining importance. In such multimedia processing, data streaming is utilized by pipelined parallel processing on successive data flow computations such as data compressions, data expansions, effect processing and soon. With this background, high throughput task scheduling for software oriented pipeline processing is expected. Scheduling issues are classified into allocations of tasks to processors, and deciding the appropriate execution orders of tasks. As there are so many solutions, these issues are called an NP hard problem. In this paper, a static task allocation method for stream-based computations using a Genetic Algorithm (GA) is proposed. In our proposed method, in order to find global solutions efficiently, a list-scheduling algorithm and a GA are adopted, and both are combined together. Finally, we show that our proposed method gives better allocation results compared with a conventional CP/MISF method.
一般社団法人情報処理学会の論文
1999-12-15