18.4 DATA SCHEDULING
Data scheduling assigns a time index value to any point in the dependence graph of Fig. 18.1. We use an affine scheduling function to specify the scheduling of the algorithm tasks. The affine scheduling functions are of the form [86]
where s = [s1 s2] is the scheduling vector and s is an integer.
Assigning time values to the nodes of the dependence graph transforms the dependence graph to a directed acyclic graph (DAG) as was discussed in Chapters 10 and 11. More specifically, the DAG can be thought of as a serial–parallel algorithm (SPA) where the parallel tasks could be implemented using a thread pool or parallel processors for software or hardware implementations, respectively. The different stages of the SPA are accomplished using barriers or clocks for software or hardware implementations, respectively.
Our choice for the scheduling vector is determined by any data input/output (I/O) requirements. Since the divisor polynomial is typically of low order, we can store its coefficients in memory and only treat A as an input polynomial supplied by the system generating the data to be compressed. From the figure, it appears that coefficient ai of A is supplied to the dependence graph at the rightmost edge at point
Get Algorithms and Parallel Computing now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
