NDLI: Module scheduling with reduced register pressure

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

Module scheduling with reduced register pressure

Content Provider	IEEE Xplore Digital Library
Author	Llosa, J. Valero, M. Agyuade, E. Gonzalez, A.
Copyright Year	1968
Abstract	Software pipelining is a scheduling technique that is used by some product compilers in order to expose more instruction level parallelism out of innermost loops. Module scheduling refers to a class of algorithms for software pipelining. Most previous research on module scheduling has focused on reducing the number of cycles between the initiation of consecutive iterations (which is termed II) but has not considered the effect of the register pressure of the produced schedules. The register pressure increases as the instruction level parallelism increases. When the register requirements of a schedule are higher than the available number of registers, the loop must be rescheduled perhaps with a higher II. Therefore, the register pressure has an important impact on the performance of a schedule. This paper presents a novel heuristic module scheduling strategy that tries to generate schedules with the lowest II, and, from all the possible schedules with such II, it tries to select that with the lowest register requirements. The proposed method has been implemented in an experimental compiler and has been tested for the Perfect Club benchmarks. The results show that the proposed method achieves an optimal II for at least 97.5 percent of the loops and its compilation time is comparable to a conventional top-down approach, whereas the register requirements are lower. In addition, the proposed method is compared with some other existing methods. The results indicate that the proposed method performs better than other heuristic methods and almost as well as linear programming methods, which obtain optimal solutions but are impractical for product compilers because their computing cost grows exponentially with the number of operations in the loop body.
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	625
Ending Page	638
Page Count	14
File Size	610398
File Format	PDF
ISSN	00189340
Volume Number	47
Issue Number	6
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1998-06-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	Processor scheduling Registers Pipeline processing Parallel processing Software algorithms Scheduling algorithm Computer Society Benchmark testing Linear programming Program processors
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

Register constrained modulo scheduling

Optimal chaining in expression trees

The importance of prepass code scheduling for superscalar and superpipelined processors

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

Resource-constrained software pipelining

On the complexity of scheduling problems for parallel/pipelined machines

On Periodic Register Need in Software Pipelining

Stability-based algorithms for high-level synthesis of digital ASICs

OPSILA: a vector and parallel processor

Module scheduling with reduced register pressure

Similar Documents

Register constrained modulo scheduling

Optimal chaining in expression trees

The importance of prepass code scheduling for superscalar and superpipelined processors

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

Resource-constrained software pipelining

On the complexity of scheduling problems for parallel/pipelined machines

On Periodic Register Need in Software Pipelining

Stability-based algorithms for high-level synthesis of digital ASICs

OPSILA: a vector and parallel processor

Module scheduling with reduced register pressure