Academic
Publications
Parallelization of while loops in nested loop programs for shared-memory multiprocessor systems

Parallelization of while loops in nested loop programs for shared-memory multiprocessor systems,Procedia Engineering,Stefan J. Geuns,Marco J. G. Bekoo

Parallelization of while loops in nested loop programs for shared-memory multiprocessor systems   (Citations: 1)
BibTex | RIS | RefWorks Download
Many applications contain loops with an undeter- mined number of iterations. These loops have to be parallelized in order to increase the throughput when executed on an em- bedded multiprocessor platform. This paper presents a method to automatically extract a parallel task graph based on function level parallelism from a sequential nested loop program with while loops. In the parallelized task graph loop iterations can overlap during execution. We introduce the notion of a single assignment section such that we can exploit single assignment to overlap iterations of the while loop during the execution of the parallel task graph. Synchronization is inserted in the parallelized task graph to ensure the same functional behavior as the sequential nested loop program. It is shown that the generated parallel task graph does not introduce deadlock. A DVB-T radio receiver where the user can switch channels after an undetermined amount of time illustrates the approach.
Journal: Procedia Engineering , pp. 1-6, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...To preserve functional correctness, synchronization statements are inserted into the generated parallel task graph using the method described in [13]...
    • ...There is also a constraint on the life-time of a value written in a variable by means of a Single Assignment Section (SAS) [13]...
    • ...The parallelism from the program body is extracted and modeled using the techniques presented in [5], [13]...
    • ...The CBs in combination with the method for the insertion of synchronization also results in a parallel task graph that is functionally equivalent to the sequential specification, as is shown in [13]...
    • ...In the case that an access pattern is non-manifest, the CSDF model must be made conservatively and may cause the model to deadlock whereas the task graph will not deadlock, as shown in [13]...
    • ...This is needed because all windows must be moved an equal number of times [13], otherwise one window might prevent that other windows can move...

    Stefan J. Geunset al. Mapping of modal applications given throughput and latency constraints

Sort by: