Instruction-Level Parallelism

Instruction-Level Parallelism is a topic that heavily relates architecture organization and compilation techniques. Related with this topic we are working in different areas:

ICTINEO: A compiler for ILP research . We are working on the implementation of a research tool to support our research on topics related with Instruction Level Parallelism. The tool, named ICTINEO is implemented on top of Polaris (from CSRD, University of Illinois at Urbana- Champaign). The key feature of ICTINEO is its high-level internal representation that allows us to do both high and low-level transformations and optimizations in a unified way. A description of the internal representation can be found in:

• Eduard Ayguadé, Cristina Barrado, Antonio González, Jesús Labarta, David López, Josep Llosa, Susana Moreno, David Padua, Fermín J. Reig, and Mateo Valero. Ictineo: A Tool for Research on ILP. In Supercomputing'96 , Pittsburgh (USA), November 1996. Research Exhibit: "The Polaris Compiler: Use in Research and Education".

• Eduard Ayguadé, Cristina Barrado, Jesús Labarta, Josep Llosa, David López, Susana Moreno, David Padua, Enric Riera, and Mateo Valero. ICTÍNEO: Una Herramienta para la Investigación en Paralelismo a Nivel de Instrucciones . In VI Jornadas de Paralelismo , pp. 53-61, Barcelona (Spain), July 1995.

• Eduard Ayguadé, Cristina Barrado, Jesús Labarta, David López, Susana Moreno, David Padua, and Mateo Valero. A Uniform Representation for High-level and Instruction-Level Transformation . Technical Report UPC-CEPBA-95-01, European Center for Parallelism of Barcelona (UPC), 1995. Also published as UPC-DAC-95-02.

Register Requirements and Software Pipelining . Software pipelining is a loop scheduling technique that extracts parallelism from loops by overlapping the execution of several consecutive iterations. Agressive scheduling techniques such are software pipelining tend to increase the register requirements. We have evaluated the register requirements of software pipelined loops, and the effects on performance of the latency and number of functional units. As a result we have proposed novel software pipelining techniques that try to obtain schedules with minimum register requirements while producing near-optimal schedules in terms of throughput:

• Josep Llosa, Antonio González, Eduard Ayguadé, and Mateo Valero. Swing Modulo Scheduling: A Lifetim-Sensitive Approach . In IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques (PACT'96) , pp. 80-86, Boston (USA), October 1996.

• José González and Antonio González. Identifying Contributing Factors to ILP . In 22nd Euromicro Conference , Prague (Czech Republic), September 1996.

• Josep Llosa, Mateo Valero, Eduard Ayguadé, and Antonio González. Hypernode Reduction Modulo Scheduling . In 28th Annual IEEE/ACM International Symposium on Microarchitecture (Micro-28) , pp. 350-360, Ann Arbor, Michigan (USA), November 1995.

• Josep Llosa, Mateo Valero, and Eduard Ayguadé. Bidirectional Scheduling to Minimize Register Requirements . In 5th Workshop on Compilers for Parallel Computers , pp. 534-554, Málaga (Spain), June 1995.

• Josep Llosa. Heuristics for Register Constrained Software Pipelining. Technical Report UPC-DAC-95-34, Departament Arquitectura de Computadors (UPC), 1995. Also published as UPC-CEPBA-95-23.

• Josep Llosa, Mateo Valero, Eduard Ayguadé, and Jesús Labarta. Register Requirements of Pipelined Loops and their Effect on Performance . In 2nd International Workshop on Massive Parallelism: hardware, Software and Applications , pp. 173-189, Capri (Italy), October 1994.

Register file organizations . Despite of the efforts for producing schedules with minimum register requirements, the continuous grow on the instruction level parallelism that can be exploited in existing processors claims for a high number of available registers in future designs. Unfortunately having a high number of registers, as well as a high number of access ports to them has its drawbacks on the area required to implement them, and their access time. We have proposed several register file organizations in order to have a high number of registers, with a fast access time, and requiring less area than an equivalent multiported register file.

• Josep Llosa, Mateo Valero, and Eduard Ayguadé. Non-Consistent Dual Register Files to Reduce Register Pressure . In Proceedings of the First International Symposium on High Performance Computer Architecture (HPCA'95) , pp. 22-31, Raleigh, North Carolina (USA), January 1995.

• Josep Llosa, Mateo Valero, José A.B. Fortes, and Eduard Ayguadé. Using Sacks to Organize Registers in VLIW Machines . In Joint International Conference on Vector and Parallel Processing (CONPAR'94 - VAPP VI) , pp. 628-639, Linz (Austria), September 1994. Lecture Notes in Computer Science #854.

PhD Thesis on ILP .

• Josep Llosa. Reducing the impact of register pressure on software pipelined loops . PhD thesis, Universitat Politècnica de Catalunya (UPC), February 1996. Advisors Mateo Valero and Eduard Ayguadé.

This thesis deals with the high register requirements of software pipelined loops and their effects on performance. The work proposes several heuristics to perform register-constrained software pipelining. In order to reduce the performance penalty caused by register constraints, it proposes a new software pipelining technique that produces near-optimal schedules with low register requirements. Finally it proposes several register file organizations with the goal of having a large number of registers without degrading the access time and the area required to implement them.