Resumen de Perfomance optimization of elastic systems
Dmitry Bufistov
An Elastic System (ES) is a set of interconnected computational nodes. The main property of the computational nodes in an ES is that they synchronize their behavior by local hand-shake protocols. That is, the behavior of a particular node depends only on its neighbors. If some input data is not available, the node waits for it as long as necessary.
Most computational systems one can imagine are elastic: a computer program, a microprocessor or an asynchronous circuit are elastic, while conventional synchronous circuits are not. In synchronous design (SD) it has to be guaranteed that all data are available at the end of the clock period. If some node fails to finish the computation, the result of the operation can be wrong. The advantage of the SD approach is that design process is more simple.
As technology continues to scale down, the uncertainty of delays of communications increases. To meet the timing requirements for some communications a the late design stages, the cycle period may need to be increased degrading the performance of the circuit. One solution for this problem is to substitute the global clock by local hand-shakes, leading to asynchronous design. However, contemporary Computer Aided Design tools are mostly oriented to the SD since it has predominated for more than twenty years.
SD can be elasticized by associating control information with the data path of the circuit. The control information indicates the validity of the data that is being transferred or computed and coordinates the flow of valid and non-valid data.
ESs accept a set of correct-by-construction transformations. Usually, such transformations can be totally automated. For example, in the ES the long interconnection wires can be pipe-lined with empty registers (bubbles).
A lot of investigation has been done in this area. However, most of the work is focused either on design aspects or on a local transformation that can potentially improve the performance of an ES and there are quite few publications about global performance optimization of ESs using proposed local transformations.
The main goal of this work is to show how the performance of an ES can be estimated and enhanced using a set of correct-by-construction transformations. This work uses a simple abstract model to represent an ES. This model is a graph with several properties attached to its vertices and edges. The simple models allow using rigorous mathematical methods for performance analysis and optimization.
The first contribution of this work combines retiming with recycling (insertion of bubbles) to optimize the performance of ESs. An optimization technique is proposed based on mixed integer linear programming. For this, the performance of ESs is modeled with a set of linear inequalities. The experimental results showed that the simultaneous application of both techniques allows achieve better performance/area trade-offs that their separate application.
There are situations when a computational node of an ES may produce new valid data having only some valid inputs. A special evaluation rule which is called early evaluation (EE) may improve the global performance of an ES when applied to multiplexer like nodes. The second contribution extends the first contribution to the ESs with EE nodes. The extension is based on the guarded marked graphs. The retiming and recycling applied to ESs with EE nodes improves their performance far beyond both retiming and clock skew optimization techniques.
The first and the second contributions assume that all buffers of the ES have infinite capacity. The third contribution shows how the reasonable sizes for these buffers can be found. To do this, slack matching and buffer sizing were combined in a mixed integer programming based model. Even, in general case, being NP-hard problem, slack-matching and buffer sizing can be applied within a few seconds to the major part of ESs.
