On Instruction-Set Generation for Real-Time Processors

Gero Dittmann

Abstract

Pattern Libraries

Many automated design methods for application-specific instruction-set processors (ASIPs) today employ a library of patterns that represent potential specialized instructions. In current approaches, the libraries are unordered data collections with search times of O(n * p), where n is the total number of operation nodes of all patterns in the library and p the size of the pattern sought. As the libraries tend to grow large their access times become a critical factor.

We propose a hierarchical organization for pattern libraries that removes the dependency of search times on the library size [3]. We introduce insert and search strategies with only O(d) and d =< p. Our experiments confirm speed-up factors of up to 1743 compared to the common unordered libraries. In this way, much larger libraries can be handled which removes the need for heuristics to prune patterns from the library. Exact methods become possible. Furthermore, we propose a second graph that employs identity operations to reveal synergies between patterns [4]. The synergies can be exploited in instruction-set synthesis, data-path sharing, and code generation. Both library graphs can easily be superimposed to combine fast searching with synergy detection in a pattern library.

Real-Time Instruction Sets

Another deficiency in today's ASIP design methodologies is their exclusive focus on the data-dominated domain characterized by computation-intensive applications such as digital signal processing. This leads to lack of methods for control-dominated domains such as network processing [1,2]. These domains are characterized by branch-intensive applications with fine-grained timing constraints. The major challenge here is not to speed up the over-all runtime of the applications, but to meet the many timing constraints that are imposed by frequent interactions with the ASIP environment. This challenge can only be met by introducing special instructions that speed up the timing-critical paths.

We introduce the first integrated ASIP design methodology for the control-dominated domain. In order to fully capture applications from this domain, we propose novel methods to specify fine-grained timing constraints in ANSI C. We represent the timing constraints in a new timing layer for an intermediate representation (IR) that facilitates standard compiler transformations [5]. Based on the IR we introduce algorithms to derive an instruction set that enables the ASIP to meet the timing constraints. We formulate two consecutive optimization problems in the form of integer linear programs to optimize the instruction set for low implementation complexity. For improved synthesis speed we also give heuristics for both optimizations. Finally, we present a case study that demonstrates the feasibility of our methods and the quality of the results.

Bibliography

1

Maria Gabrani, Gero Dittmann, Andreas Doering, Andreas Herkersdorf, Patricia Sagmeister, and Jan van Lunteren.
Design methodology for a modular service-driven network processor architecture.
Computer Networks, 41(5):623-640, April 2003.

2

David E. Taylor, Andreas Herkersdorf, Andreas Doering, and Gero Dittmann.
Robust header compression (ROHC) in next-generation network processors.
To appear in IEEE/ACM Transactions on Networking, October 2005.

3

Gero Dittmann.
Organizing libraries of DFG patterns.
In Proceedings of Design, Automation and Test in Europe (DATE'04), Paris, France, February 2004.

4

Gero Dittmann.
Pattern libraries for fast searching and data-path sharing.
In Proceedings of the 3rd Workshop on Application Specific Processors (WASP), pages 76-83, Stockholm, Sweden, September 2004.

5

Gero Dittmann and Andreas Herkersdorf.
Fine-grained timing constraints for reactive systems in ANSI C.
In Proceedings of the 25th IEEE International Real-Time Systems Symposium (RTSS 2004) - WIP Session, Lisbon, Portugal, December 2004.

  

START Conference Manager (V2.49.3)

Maintainer: rrgerber@softconf.com