NDLI: Optimizing Bandwidth Constraint through Register Interconnection for Stream Processors

Content Provider	IEEE Xplore Digital Library
Author	Weihua Zhang Tao Bao Binyu Zang Chuanqi Zhu
Copyright Year	2007
Description	Author affiliation: Fudan Univ., Shanghai (Weihua Zhang; Tao Bao; Binyu Zang; Chuanqi Zhu)
Abstract	In recent years, multimedia and game applications have experienced rapid growth at an explosive rate both in quantity and complexity. Since these applications typically demand 1010 to 1011 operations to be executed per second, higher processing capability is expected. Therefore, stream processors are becoming popular because of its performance advantages in the domains of signal processing, multimedia and etc. To provide sufficient computing capability, multi-SIMD units are employed in the stream processors. Moreover, to overcome the centralized register file constraint, hierarchical register organization is proposed and widely used in stream processors. In upper level of the hierarchy, distributed register file (DRF) becomes the dominant design and there are explicit interconnections among the DRFs managed by the compiler in a VLIW manner. Moreover, in order to further exploit the nice locality characteristics in multimedia applications, the lower level is a multi-banked register file where each bank is accessed by several SIMD units through a shared data bus. We will refer to the architecture with such characteristics as MLRM- SIMD architecture. Although such a design suits for multimedia processing, low data bandwidth caused by the shared data bus between multi-level registers severely impedes the programs mapping to MLRM-SIMD architecture. If this constraint can not be resolved well, the parallelism among multi-SIMD units would also be influenced as well as the whole program performance. Therefore, one of the major challenges to optimizing techniques for MLRM-SIMD architecture is to resolve the shared bus conflicts well. However, when generating the executable codes for MLRM-SIMD architecture, the compiler must simultaneously allocate many interdependent resources: the SIMD units on which the operations take place, the register files to hold the intermediate values and the shared bus to transfer the data for SIMD units. These conditions put very high pressure on the optimizing algorithms. Although read-read reuse operands among different SIMD units can be replicated, replicating all data would increase the register pressure and data spilling and reloading would also lead to the data bus conflicts. As there are interconnections among DRFs, some optimizations can be performed to improve the low data bandwidth. If the data is not required by many different SIMD units at the same time, they can be loaded by one SIMD unit only and transferred to other SIMD units through the interconnection between registers while being required. Such a manner would bring no data bus conflict and less local register pressure because only one data copy is saved in the DRFs. It is the major motivation of our optimizing algorithm. In this paper, we present a novel data pipeline optimization through communicating read-read source operands among different SIMD units to reduce the shared data bus conflicts. We use loop level parallelism to exploit the multi- SIMD computing ability and use read-read reuse communication to reduce the data bus conflicts. In contrast, traditional pipeline algorithms usually exploit pipeline parallelism and communicate computing results of prior stages. Therefore, we refer to our algorithm as data pipeline scheduling to distinguish it from traditional pipeline algorithm. Such a policy not only reduces the bus conflict, but also releases the register pressure. Experimental results show that it improves performance by 12% over the traditional method based on replication only. Based on the experimental results, some advice on programming is proposed for MLRM-SIMD architecture. When writing programs for MLRM-SIMD architecture, it is better to maintain the original structure in the algorithms, which would be much easier for compilers to exploit the parallelism in the programs and thus generate more efficient executable codes.
Starting Page	434
Ending Page	434
File Size	62964
Page Count	1
File Format	PDF
ISBN	9780769529448
ISSN	1089795X
DOI	10.1109/PACT.2007.4336262
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-09-15
Publisher Place	Romania
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Constraint optimization Bandwidth Registers Streaming media Pipelines Parallel processing Concurrent computing Scheduling algorithm Explosives Signal processing
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Hardware and Architecture Software

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

Global register partitioning

Architecture-dependent register allocation and instruction scheduling on VLIW

Programmable stream processors

Stream register files with indexed access

Heuristics for register-constrained software pipelining

Media processing applications on the Imagine stream processor

A new heuristic for scheduling parallel programs on multiprocessor

Register File Partitioning with Constraint Programming

Module scheduling with reduced register pressure

Optimizing Bandwidth Constraint through Register Interconnection for Stream Processors

Similar Documents

Global register partitioning

Architecture-dependent register allocation and instruction scheduling on VLIW

Programmable stream processors

Stream register files with indexed access

Heuristics for register-constrained software pipelining

Media processing applications on the Imagine stream processor

A new heuristic for scheduling parallel programs on multiprocessor

Register File Partitioning with Constraint Programming

Module scheduling with reduced register pressure

Optimizing Bandwidth Constraint through Register Interconnection for Stream Processors