An arithmetic pipeline is designed to process more than one task simultaneously in an overlap- ping manner. It includes function units and data paths among them. Tasks are processed by pipelining; at each clock, one or more units are dedicated to a task and the output produced for the task at the clock is cascading to the units that are responsible for the next stage; since each unit may work in parallel with the others at any clock, more than one task may be being processed at a time by a single pipeline. In this problem, a pipeline may have a feedback structure, that is, data paths among function units may have directed loops as shown in the next figure. Example of a feedback pipeline Since an arithmetic pipeline in this problem is designed as special purpose dedicated hardware, we assume that it accepts just a single sort of task. Therefore, the timing information of a pipeline is fully described by a simple table called a reservation table, which specifies the function units that are busy at each clock when a task is processed without overlapping execution. Example of “reservation table” clock 0 1 2 3 4 5 6 unit0 X . . . X X . unit1 . X . . . . . unit2 . . X . . . . unit3 . . . X . . . unit4 . . . . . . X In reservation tables, ‘X’ means “the function unit is busy at that clock” and ‘.’ means “the function unit is not busy at that clock.” In this case, once a task enters the pipeline, it is processed by unit0 at the first clock, by unit1 at the second clock, and so on. It takes seven clock cycles to perform a task. Notice that no special hardware is provided to avoid simultaneous use of the same function unit. Therefore, a task must not be started if it would conflict with any tasks being processed. For instance, with the above reservation table, if two tasks, say task 0 and task 1, were started at clock 0 and clock 1, respectively, a conflict would occur on unit0 at clock 5. This means that you should not start two tasks with single cycle interval. This invalid schedule is depicted in the following process table, which is obtained by overlapping two copies of the reservation table with one being shifted to the right by 1 clock. Example of “conflict” clock 0 1 2 3 4 5 6 7 unit0 0 1 . . 0 C 1 . unit1 . 0 1 . . . . . unit2 . . 0 1 . . . . unit3 . . . 0 1 . . . unit4 . . . . . . 0 1
unit0 | 0..100211322433544655766877988.99. unit1 | .0..1..2..3..4..5..6..7..8..9..... unit2 | ..0..1..2..3..4..5..6..7..8..9.... unit3 | ...0..1..2..3..4..5..6..7..8..9... unit4 | ......0..1..2..3..4..5..6..7..8..9 (The digits in the table except those in the clock row represent the task number.) This is the best possible schedule and therefore your program should report 34 in this case.
3/3 Sample Input 7 X...XX. .X..... ..X.... ...X... ......X 0 Sample Output 34