Global Sources
EE Times-India
Stay in touch with EE Times India
EE Times-India > Processors/DSPs

Boost ASIP code generation, compilation (Part 2)

Posted: 06 Sep 2013     Print Version  Bookmark and Share

Keywords:Instruction selection  DSPs  ASIPs  FlexWare  compiler 

Instruction selection becomes vital when the processor has limited or irregular resources. Many DSPs have irregular register sets and operations, so instruction selection becomes very important for these machines. Limited or irregular processor resources are also influential when operations are performed. Instruction selection and scheduling may interact as a result of resource limitations.

As part of the FlexWare system, Liem et al. [7] developed an instruction generation system for ASIPs with irregular register files. Figure 1 shows the intermediate representation for programs, which includes both data and control flow aspects.

Figure 1: Program representations for FlexWare.

Target instructions are described in the same basic format. Each instruction is annotated with register classes that identify how registers can communicate with each other. To cover the program graph with instructions, they use dynamic programming for the data flow segments and heuristics for the control flow parts of the graph.

The second-generation FlexWare compiler [8] generates code in three main stages. It first uses rule-based techniques such as those just described to select instructions. It then performs peephole optimisations on the code. Finally, it compacts the code to create a schedule for the operations and generates assembly language.

The PEAS-III compiler generator as described in Kobayashi et al. [3] creates mapping rules based on instruction descriptions. It classifies instructions into five categories: arithmetic/logical, control, load/store, stack manipulation, and special. The compiler generator creates scheduling information by tracing how each instruction uses pipeline resources, then calculating the latency and throughput of each instruction.

Mesman et al. [9] developed a model for the constraints on code scheduling. Constraints determine the set of feasible times when operations can be scheduled; the feasible schedule space can be searched to find the desired schedule. They represent the set of constraints as a weighted directed graph. Vertices in the graph represent operations, and edges represent precedence relationships. The constraints can also be written as linear inequalities, as shown in figure 2. Each node is constrained against the other.

Figure 2: Constraint graphs and linear inequalities.

Mesman et al. consider several types of constraints. Data dependencies are represented by a single edge whose weight is equal to the operation's execution time. If the data dependency is in a loop, the value must be consumed before the next iteration; a backward arc for each data dependency represents this requirement.

Other types of latencies are also represented by single edges. Multicycle operations are represented using one node per stage of execution. They use 0–1 variable to model resource conflicts. To solve the system of constraints and find a schedule, they add edges to the graph to fix the times of operations. For example, potential resource conflicts are avoided by adding an edge that ensures the operations are not scheduled at the same time.

Constraints are also added to ensure that all the operations in a subgraph have time to execute. In addition, edges can be added to make variable lifetimes sequential.

Figure 3: A register transfer graph.

Araujo and Malik [10] developed an optimal algorithm for instruction selection, register allocation, and scheduling on a class of architectures in which either one location or an unbounded number of those of a given class is available. The TI TMS320C25 is an example of this class. They define this class using a register transfer graph: each node in the graph is a register or main memory; a directed edge from one node to another indicates a possible data transfer, with a label on the edge that defines which instruction(s) can perform the transfer. An example of such a register transfer graph is shown in figure 3: the r3 register can be written from both r1 and r2 using the l instruction; all the cycles between r1 and r2 include the memory node. This condition ensures that values can be spilled to main memory when needed. Based on this property, Araujo and Malik showed that expression trees can always be scheduled without a memory spill.

1 • 2 • 3 Next Page Last Page

Comment on "Boost ASIP code generation, compilat..."
*  You can enter [0] more charecters.
*Verify code:


Visit Asia Webinars to learn about the latest in technology and get practical design tips.


Go to top             Connect on Facebook      Follow us on Twitter      Follow us on Orkut

Back to Top