Donald Bren School of Information and Computer Sciences

Multiple functional unit architectures have become increasingly widespread since they represent a viable design technique that allows to boost performance by concurrently executing many operations. Technology, though, allows the design of register files providing enough data-!bandwidth to support only few fast pipelined functional units.

One of the possible solutions is to partition the set of registers in multiple banks, each providing only part of the overall bandwidth required, and connect them to functional units by mean of a network.

This design scheme provides a non homogeneous register space requiring code with variables partitioned among the set of register files. Standard register allocation techniques are not suited for this task because of the different kind of resources that must be taken into consideration.

In this report we present a hypergraph-based paradigm that allows to model the process of partitioning; a coloring algorithm is used to assign variables to register files and if a legal coloring is not found, the code is partially rescheduled to allow the algorithm to proceed.

Experiments ran on a set of benchmarks show how the technique can frequently find a legal partitioning of variables without the needs for rescheduling; even when this is not possible, and code must be reorganized, very little performance degradation is usually introduced.