NDLI: Minimum register instruction sequencing to reduce register spills in out-of-order issue superscalar architectures

Please wait, while we are loading the content...

Minimum register instruction sequencing to reduce register spills in out-of-order issue superscalar architectures

Content Provider	IEEE Xplore Digital Library
Author	Govindarajan, R. Hongbo Yang Amaral, J.N. Chihong Zhang Gao, G.R.
Copyright Year	1968
Abstract	In this paper, we address the problem of generating an optimal instruction sequence S for a Directed Acyclic Graph (DAG), where S is optimal in terms of the number of registers used. We call this the Minimum Register Instruction Sequence (MRIS) problem. The motivation for revisiting the MRIS problem stems from several modern architecture innovations/requirements that has put the instruction sequencing problem in a new context. We develop an efficient heuristic solution for the MRIS problem. This solution is based on the notion of instruction lineage-a set of instructions that can definitely share a single register. The formation of lineages exploits the structure of the dependence graph to facilitate the sharing of registers not only among instructions within a lineage, but also across lineages. Our efficient heuristics to "fuse" lineages further reduce the register requirement. This reduced register requirement results in generating a code sequence with fewer register spills. We have implemented our solution in the MIPSpro production compiler and measured its performance on the SPEC95 floating point benchmark suite. Our experimental results demonstrate that the proposed instruction sequencing method significantly reduces the number of spill loads and stores inserted in the code, by more than 50 percent in each of the benchmarks. Our approach reduces the average number of dynamic loads and stores executed by 10.4 percent and 3.7 percent, respectively. Further, our approach improves the execution time of the benchmarks on an average by 3.2 percent. In order to evaluate how efficiently our heuristics find a near-optimal solution to the MRIS problem, we develop an elegant integer linear programming formulation for the MRIS problem. Using a commercial integer linear programming solver, we obtain the optimal solution for the MRIS problem. Comparing the optimal solution from the integer linear programming tool with our heuristic solution reveals that, in a very large majority (99.2 percent) of the cases, our heuristic solution is optimal. For this experiment, we used a set of 675 dependence graphs representing basic blocks extracted from scientific benchmark programs.
Sponsorship	IEEE Computer Society Technical Committee on Distributed Process IEEE Computer Society Technical Committee on VLSI IEEE Technical Committee on Computer Architecture IEEE Computer Society
Starting Page	4
Ending Page	20
Page Count	17
File Size	1088401
File Format	PDF
ISSN	00189340
Volume Number	52
Issue Number	1
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2003-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Out of order Magnetic resonance imaging Registers Integer linear programming Parallel processing Runtime Hardware Technological innovation Production Processor scheduling
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Software Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Microarchitecture of a Coarse-Grain Out-of-Order Superscalar Processor

Hybrid-Scheduling for Reduced Energy Consumption in High-Performance Processors

Efficient exploitation of instruction-level parallelism for superscalar processors by the conjugate register file scheme

Exploiting Application Data-Parallelism on Dynamically Reconfigurable Architectures: Placement and Architectural Considerations

Leveraging Register Windows to Reduce Physical Registers to the Bare Minimum

Module scheduling with reduced register pressure

Scheduled dataflow: execution paradigm, architecture, and performance evaluation

Scheduled dataflow: execution paradigm, architecture, and performance evaluation

Design space exploration of hardware task superscalar architecture

Minimum register instruction sequencing to reduce register spills in out-of-order issue superscalar architectures

Similar Documents

Microarchitecture of a Coarse-Grain Out-of-Order Superscalar Processor

Hybrid-Scheduling for Reduced Energy Consumption in High-Performance Processors

Efficient exploitation of instruction-level parallelism for superscalar processors by the conjugate register file scheme

Exploiting Application Data-Parallelism on Dynamically Reconfigurable Architectures: Placement and Architectural Considerations

Leveraging Register Windows to Reduce Physical Registers to the Bare Minimum

Module scheduling with reduced register pressure

Scheduled dataflow: execution paradigm, architecture, and performance evaluation

Scheduled dataflow: execution paradigm, architecture, and performance evaluation

Design space exploration of hardware task superscalar architecture

Minimum register instruction sequencing to reduce register spills in out-of-order issue superscalar architectures