Research On Mapping Algorithms For Embedded Stream Applications On Many-core Platforms By ANT Colony Optimization

Many-core system-on-chips proliferate rapidly in recent years, but the correspondinginfrastructure software and their programming methodology develop slowly. As a branch of theembedded software, stream applications rich with natural parallelism are widely used incommunication device, multimedia, radar signal processing and so on. The automated synthesis ofstream applications on many-core platforms is one of the research hotspots currently. Because ofthe diversity of many-core platforms and its complexity of task mapping problem, the existingsolutions should be improved on the solving speed and accuracy, which still need further researchand exploration.Firstly, the main models of many-core platforms are classified and analyzed comparatively inthis paper, and then an in-depth study of all main steps of stream applications synthesis techniqueon multi-core platforms is also made. By the summarization of relationships among its steps, thekey issue of each of those steps and its current research status, the basic process of streamapplications synthesis technique was summed up. Due to the shortcomings existed in recentresearch results of stream applications mapping strategies, two key problems, to be deal with inthis paper, were put forward: one was to tackle task mapping strategy treating the tasks executionspan as the optimization goal, while the other considering both the tasks execution span and theamount of used buffer simultaneously as the optimization goal.Secondly, a task mapping algorithm of optimal tasks execution span on many-core platformbased on ant colony optimization is developed. Regarding application execution span as theoptimization target, it not only improved the updating rule of the pheromone in the basic antcolony optimization, but also put forward a calculation method for the real time heuristicinformation aiming at the optimization goal. Moreover, it innovatively determined the scheduling sequence while establishing the task allocation scheme. Experiments prove that the task mappingschema determined by this algorithm takes a good effect in optimizing the execution span ofstream application. Compared with simulated annealing algorithm, it had a great advantage infinal result accuracy and convergence rate.Lastly, a task mapping algorithm with the double optimization goals of execution span andon-chip buffer is presented considering the limited resource of embedded platform. On the basis ofanalyzing the basic theory and the previous solutions of multi-objective optimization, thealgorithm converted this problem to the optimization of objective cost function by using the priorpriority method. Furthermore, by analyzing the model of many-core platform and streamapplication to characterize the buffer changes in the stream program executing process, somespecific implementation details, such as the initialization, the calculation method of real-timeheuristic value, are set forth. Experiments show that, by contrast with the negative effect causedby single-object optimization algorithm that the total cost value is too large, this algorithm reducesthe total cost by achieving the control of the two optimization objects. And it also yields betterresults when compared with the simulated annealing algorithm.In this paper, we attempt to resort to ant colony algorithm, a heuristic algorithm, to solve aninstance of NP-hard problems, and the research results may have some practical value in theinfrastructure software designing for many-core system-on-chips.