First, we designed techniques to deal with control hazards because of branches which may give pipeline hazards and degrade the performance on the underlying pipelined architecture. We studied the theory, supporting hardware and experiments of a novel technique, based on multi-dimensional retiming, for removing control stalls caused by branches within nested loops. This technique, called Multi-Dimensional Branch Anticipation Scheduling, is able to achieve optimal or near-optimal schedule length for nested loops containing branch instructions in polynomial time. Since the branch instructions are scheduled to correct positions forward enough, the control stalls can be completely eliminated. The technique transforms a multi-dimensional conditional data flow graph representing the nested loop, carries out loop pipelining and conditional resource sharing, breaks sharing-prevention cycles and minimizes additional hardware requirements incurred by propagation of branch control signals along the schedule. Such propagation is accomplished by specially designed component, Branch Anticipation Bits (BABITs). The hardware complexity of branch anticipation control logic is affordable. The experiments show that the technique achieves better results than any other previously known methods.
We also developed a technique to deal with data hazards. Data hazards are a major obstacle against the high performance of pipelined systems. We gave a novel efficient loop scheduling algorithm that reduces data hazards for DSP applications. This algorithm has been embedded in a tool, called SHARP, which schedules a pipelined data flow graph to multiple pipelined units while hiding the underlying data hazards and minimizing the execution time. We showed that significant improvement for some well-known benchmarks, and the flexibility of the simulation tool.
Two journal papers were published under this category.