Latest revision as of 17:20, 28 January 2021

Abstract

mini-graph is a dataflow graph that has an arbitrary internal size and shape but the interface of a singleton instruction: two register inputs, one register output, a maximum of one memory operation, and a maximum of one (terminal) control transfer. Previous work has exploited dataflow sub-graphs whose execution latency can be reduced via programmable FPGA-style hardware. In this paper we show that mini-graphs can improve performance by amplifying the bandwidths of a superscalar processor's stages and the capacities of many of its structures without custom latency-reduction hardware. Amplification is achieved because the processor deals with a complete mini-graph via a single quasi-instruction, the handle. By constraining mini-graph structure and forcing handles to behave as much like singleton instructions as possible, the number and scope of the modifications over a conventional superscalar microarchitecture is kept to a minimum. This paper describes mini-graphs, a simple algorithm for extracting them from basic block frequency profiles, and a microarchitecture for exploiting them. Cycle-level simulation of several benchmark suites shows that mini-graphs can provide average performance gains of 2-12% over an aggressive baseline, with peak gains exceeding 40%. Alternatively, they can compensate for substantial reductions in register file and scheduler size, and in pipeline bandwidth.

Original document

The different versions of the original document can be found in:

• https://repository.upenn.edu/cgi/viewcontent.cgi?article=1283&context=cis_papers

• http://xplorestaging.ieee.org/ielx5/10398/33048/01550979.pdf?arnumber=1550979,

http://dx.doi.org/10.1109/micro.2004.15

• https://repository.upenn.edu/cis_papers/267,

http://repository.upenn.edu/cgi/viewcontent.cgi?article=1283&context=cis_papers,

http://www.eecg.toronto.edu/~moshovos/ACA08/readings/03_Bracy-Mini-graphs.pdf,

https://dblp.uni-trier.de/db/conf/micro/micro2004.html#BracyPR04,

https://ieeexplore.ieee.org/document/1550979,

http://www.cis.upenn.edu/acg/papers/micro04_minigraphs.pdf,

https://www.computer.org/csdl/proceedings/micro/2004/2126/00/21260018.pdf,

https://academic.microsoft.com/#/detail/2535965777