Scheduling Structured Systems
The use of subsystems is fundamental to the modeling of hierarchical hardware using recurrence equations. Scheduling adds temporal information to a system and is thus a key step in the synthesis of parallel hardware from algorithms. It determines such thi
- PDF / 61,591 Bytes
- 4 Pages / 431 x 666 pts Page_size
- 40 Downloads / 161 Views
Doran K. Wilde
Department of Electrical and Computer Engineering Brigham Young University Provo, Utah
Abstract. The use of subsystems is fundamental to the modeling of hierarchical hardware using recurrence equations. Scheduling adds temporal information to a system and is thus a key step in the synthesis of parallel hardware from algorithms. It determines such things as the placement of pipeline registers, the latency and throughput of the circuit, and the order and rate that inputs are consumed and outputs produced. This paper will show how to extend usual dependence analysis to derive the additional dependences on the timing function needed when subsystems are used.
Introduction The only practical way of representing large, complex designs is by using a structural hierarchy of modules. In this paper, we consider the problem of scheduling structured hierarchical systems of affine recurrence equations, a problem encountered during the synthesis of structured parallel hardware from structured recurrence equations. The interconnection and delays in a system constrain the time when each operation in the system can be computed. When a system is represented hierarchically, constraints between the calling system, and the system being called must also be taken into account when scheduling both systems. These constraints take the form of dependences between variables. The scheduling of systems of recurrence equations is based on constraining the coefficients of affine timing functions and then deriving coefficient values by solving a linear programming problem[4,5]. Scheduling adds temporal information to a system and is thus an important step in the process of synthesizing parallel hardware from algorithms. It determines such things as the placement of pipeline registers, the latency and throughput of the circuit, and the order and rate that inputs are consumed and outputs produced. Scheduling of hierarchical systems can be done by flattening the structure and then scheduling. However, this leads to huge, difficult to solve linear programming problems, and defeats the advantages of structured systems. After flattening, information about program structure is lost and it is difficult to reconstitute the hierarchy. Structured scheduling is simpler and preserves the hierarchical structure. We have been using ALPHA[1,2] to model and synthesize parallel hardware. Structured hardware modules map easily onto ALPHA subsystems. Primitive hardware modules have been designed, and corresponding ALPHA models written, to implement a large set of basic arithmetic operators. When synthesizing hardware P. Amestoy et al. (Eds.): Euro-Par’99, LNCS 1685, pp. 409-412, 1999. Springer-Verlag Berlin Heidelberg 1999
410
Jason B. Crop and Doran K. Wilde
using a library of pre-designed hardware modules, the subsystems written to model library modules are necessarily pre-scheduled. We develop the scheduling constraints imposed on a calling system when it instantiates (calls) a subsystem. As part of the synthesis process, arithmetic operator
Data Loading...
