Single-phase instruction scheduling for clustered architectures
- CODINA VIÑAS, JOSE MARIA
- Antonio González Colás Directeur/trice
- Jesús Sánchez Navarro Co-directeur/trice
Université de défendre: Universitat Politècnica de Catalunya (UPC)
Fecha de defensa: 14 avril 2008
- Emilio Luque Fadón President
- David López Álvarez Secrétaire
- Agustín Fernández Jimenez Rapporteur
- Paolo Faraboschi Rapporteur
- Clemente Rodríguez Lafuente Rapporteur
Type: Thèses
Résumé
Technology evolution results in an increased number of transistors in a chip and higher clock frequencies. The incresing magnitude of wire delays imply that processors become limited by communications instead of computation capacity. The chip area reachable in a single cycle diminishes from process-to-process technology. Sending a signal from one corner of the chip to the opposite one may require several clock cycles. Clustering alleviates the impact of the signal delay problem. Clustering consists of diving the processor in several semi-independent units, where each unit is a called a cluster. Clustering also reduces power consumption and chip design complexity. The reduced delays may translate into a higher clock frequency whereas the lower complexity may reduce the power requirements. The most common clustered design consists of a system where the whole set of functional units (Fus) and the number of registers are distributed among all clusters. Thus, a cluster consists of a register file with a limited number of Fus. Communication inside each cluster is fast, whereas communications among different clusters imply the use of an inter-cluster interconnection network and additional cycles to transfer the values. Nowadays, clustered designs can be found in several domains, including high performance and low end/embedded systems. However, where this trend is more common is on the embedded/DSP domain. Statically scheduled processors, e.g. VLIW, are common in the low-end domain due to their low design complexity and the good trade-off they offer in terms of low power consumption and high performance. These processors rely on the compiler to archive high instruction-level parallelism (ILP). Probably the most critical step for performance in statistically-scheduled processors is the code generation. This step is not only the responsible for instruction scheduling and register allocation, but it must also deal with cluster assignment. Cluster assignment consists of distributing the instructions to the available clusters. The main objective of the assignment is to minimize the penalty due to slow inter-cluster communications. This class of communications occurs when a value is stored in a cluster different from the one where it is actually required. Thus, a communication among them must be scheduled. The impact of these communications depends on the interconnection speed and its bandwidth. In order to alleviate the impact of these communications it is important to perform an appropriate distribution of the workload. The generation of high-performance code depends on the techniques to perform each task in the code generation process (i.e. instruction scheduling, register allocation and cluster assignment). Besides, the order in which these tasks are done (phase-ordering) must be specially taken into account. Given a compiler that performs each of these tasks sequentially, the optimal solution may not be found even when the optimal solution is achieved for each individual task. This is due to the fact that each phase is not independent of the others. In particular, decisions taken in a former task constraint the search space that latter tasks may consider. This problem is known as the phase-ordering problem. In this thesis, novel techniques for code generation targeting statically-scheduled clustered processors have been proposed with special emphasis on the phase-ordering problem. In order to alleviate the negative effects on establishing an ordering among the tasks in code generation step, the techniques we have proposed combine all tasks together in a single-phase. More specifically, in this thesis, single-phase techniques for cycling code (i.e. loops) as well as acyclic code have been proposed.