Software Pipelining On Transport Triggered Architecture

On transport triggered architectures (TTAs) featuring huge scheduling freedom, parallelism is exploited at not only operation level, but also data transportation level. Multi-TTA cores are usually used to handle multimedia computing. Thus, HW/SW partitioning and task level pipelined scheduling are very important. Moreover, software pipelining is an aggressive compiler optimization scheme for exploiting instruction level parallelism across loop iterations. However, only few efforts were focused on the combination of these works on multi-TTA cores. In these existing works, intuitive yet less efficient methods were used, namely either modulo scheduling algorithm with some heuristics or parallel language to implement pipelined scheduling on TTA.In this paper, we formulate the problem of constructing a resource constrained rate-optimal software pipelining with minimal loop overhead on TTAs as an integer linear programming (ILP) problem. The formulated problem is solved with GNU Linear Programming Kit (GLPK). We apply our approach to major loops in Livermore loop benchmarks. Comparing with the previous schedulers implemented with list scheduling with heuristic priority function, our ILP approach creates schedules which bring significant performance enhancement to applications on TTA. We also propose a new SMT-based method to solve HW/SW partition and schedule task graph into pipelined schedule. Experimental results show our method can improve the final code quality significantly. Therefore, our two methods can be used to perform the multiple hierarchies pipelined scheduling on multi-TTA cores.