Loading...
Please wait, while we are loading the content...
Similar Documents
High-level synthesis scheduling for conditional statements
| Content Provider | Semantic Scholar |
|---|---|
| Author | Besouw, P. W. P. M. Van |
| Copyright Year | 1995 |
| Abstract | This thesis outlines several scheduling methods that emphasize conditional branching . The main idea of these algorithms is to schedule mutual exclusive operations to allow sharing of resources and possibly create a faster schedule for some paths in the control flow graph . The representations of conditional branches can broadly be classified into two types : control select and data select . In order for a scheduler to make a tradeoff between resource sharing and fast execution of mutually exclusive branches, the scheduler must have the possibility to select either of the two forms of representation. Many systems do not consider conditional resource sharing in their basic algorithms . Some systems, however, consider mutual exclusion of some operations in conditional branches. Some well known mutual exclusion testing methods are the node coloring algorithm and the condition vector technique. These algorithms, however cannot handle certain types of conditional branches correctly, and give incorrect results in some cases . These problems are overcome by the branch numbering algorithm . As-Fast-As-Possible (AFAP) is a path-based scheduling algorithm that ensures the minimum number of control steps for all possible sequences of operations in the control flow graph, under given resource constraints . This technique requires scheduling one operation into different states depending on the path . Although the worst case computational complexity is non-polynomial, there are no execution time problems in practice . The Condition Vector List Scheduling (CVLS) algorithm exploits a more "global parallelism" . That is, it can parallelize multiple nests of conditional branches and optimize across the boundaries of basic blocks. Furthermore, it can optimize all possible execution paths . Also some control sequence improvement techniques as operation node reassignment and operation node dividing are introduced. Finally, the Hierarchical Reduction Approach algorithm transforms a data flow graph with conditional branches into an "equivalent" one that has no conditional branches. A schedule is then obtained for the latter, using a conventional scheduling algorithm, from which a schedule for the former is derived . Time complexity of this algorithm is low in comparison with the other algorithms, but it does not exploit potential parallelism to the fullest . It is difficult to compare the different scheduling algorithms because the objectives of the techniques used are different . The AFAP algorithm minimizes the number of cycle steps, but the fundamental order of operations for a given path has to be chosen in advance and consequently potential parallelism of operations can easily be overlooked . Although the complexity of the Hierarchical Reduction Approach is low in comparison with the other algorithms the possibility of global resource sharing depends on the order in which the transformations are performed . The CVLS algorithm has the limitation that certain types of conditional branches cannot be handled correctly. However, these limitation are easily |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://alexandria.tue.nl/extra2/afstversl/E/657003.pdf |
| Alternate Webpage(s) | https://pure.tue.nl/ws/files/46956038/657003-1.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
