NDLI: Balancing register allocation across threads for a multithreaded network processor

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

Race checking by context inference

Scalable lock-free dynamic memory allocation

Min-cut program decomposition for thread-level speculation

Cost effective dynamic program slicing

Cloning-based context-sensitive pointer alias analysis using binary decision diagrams

Fast searches for effective optimization phase sequences

The set constraint/CFL reachability connection in practice

Region inference for an object-oriented language

A generalized algorithm for graph-coloring register allocation

Social processes and proofs of theorems and programs, revisited

KISS: keep it simple and sequential

Kill-safe synchronization abstractions

A cost-driven compilation framework for speculative parallelization of sequential programs

Dynamic path-based software watermarking

Symbolic pointer analysis revisited

Inducing heuristics to decide whether to schedule

Parametric regular path queries

Array regrouping and structure splitting using whole-program reference affinity

Balancing register allocation across threads for a multithreaded network processor

Verifying safety properties using separation and heterogeneous abstractions

Vectorization for SIMD architectures with alignment constraints

Parametric analysis for adaptive computation offloading

Jedd: a BDD-based relational extension of Java

The liberty structural specification language: a high-level modeling language for component reuse

Precise and efficient static array bound checking for large embedded C programs

Prefetch injection based on hardware monitoring and object metadata

Balancing register allocation across threads for a multithreaded network processor

Content Provider	ACM Digital Library
Author	Zhuang, Xiaotong Pande, Santosh
Abstract	Modern network processors employ multi-threading to allow concurrency amongst multiple packet processing tasks. We studied the properties of applications running on the network processors and observed that their imbalanced register requirements across different threads at different program points could lead to poor performance. Many times application needs demand some threads to be more performance critical than others and thus by controlling the register allocation across threads one could impact the performance of the threads and get the desired performance properties for concurrent threads. This prompts our work.Our register allocator aims to distribute available registers to different threads according to their needs. The compiler analyzes the register needs of each thread both at the point of a context switch as well as internally. Compiler then designates some registers as shared and some as private to each thread. Shared registers are allocated across all threads explicitly by the compiler. Values that are live across a context switch can not be kept in shared registers due to safety reasons; thus, only those live ranges that are internal to the context switch can be safely allocated to shared registers. Spill can cause a context switch. and thus, the problems of context switch and allocation are closely coupled and we propose a solution to this problem. The proposed interference graphs (GIG,BIG,IIG) distinguish variables that must use a thread's private registers from those that can use shared registers. We first estimate the register requirement bounds, then reduce from the upper bound gradually to achieve a good register balance among threads. To reduce the register needs, move insertions are inserted at program points that split the live ranges or the nodes on the interference graph. We show that the lower bound is reachable via live range splitting and is adequate for our benchmark programs for simultaneously assigning them on different threads. As our objective, the number of move instructions is minimized.Empirical results show that the compiler is able to effectively control the register allocation across threads by maximizing the number of shared registers. Speed-up for performance critical threads ranges from 18 to 24% whereas degradation for performance of non-critical threads ranges only from 1 to 4%.
Starting Page	289
Ending Page	300
Page Count	12
File Format	PDF
ISBN	1581138075
DOI	10.1145/996841.996876
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2004-06-09
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Network processor Multithreaded processor Register allocation
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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