NDLI: Synthesizing concurrent schedulers for irregular algorithms (CARN, Vol. 39, Issue. 1)

Content Provider	ACM Digital Library
Author	Nguyen, Donald Pingali, Keshav
Abstract	Scheduling is the assignment of tasks or activities to processors for execution, and it is an important concern in parallel programming. Most prior work on scheduling has focused either on static scheduling of applications in which the dependence graph is known at compile-time or on dynamic scheduling of independent loop iterations such as in OpenMP. In irregular algorithms, dependences between activities are complex functions of runtime values so these algorithms are not amenable to compile-time analysis nor do they consist of independent activities. Moreover, the amount of work can vary dramatically with the scheduling policy. To handle these complexities, implementations of irregular algorithms employ carefully handcrafted, algorithm-specific schedulers but these schedulers are themselves parallel programs, complicating the parallel programming problem further. In this paper, we present a flexible and efficient approach for specifying and synthesizing scheduling policies for irregular algorithms. We develop a simple compositional specification language and show how it can concisely encode scheduling policies in the literature. Then, we show how to synthesize efficient parallel schedulers from these specifications. We evaluate our approach for five irregular algorithms on three multicore architectures and show that (1) the performance of some algorithms can improve by orders of magnitude with the right scheduling policy, and (2) for the same policy, the overheads of our synthesized schedulers are comparable to those of fixed-function schedulers.
Starting Page	333
Ending Page	344
Page Count	12
File Format	PDF
ISSN	01635964
DOI	10.1145/1961295.1950404
Journal	ACM SIGARCH Computer Architecture News (CARN)
Volume Number	39
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1981-04-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Synthesis Scheduling
Content Type	Text
Resource Type	Article

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

Synthesizing concurrent schedulers for irregular algorithms (SIGP, Vol. 46, Issue. 3)

Synthesizing concurrent schedulers for irregular algorithms

A case for neuromorphic ISAs (CARN, Vol. 39, Issue. 1)

Deterministic galois:on-demand, portable and parameterless (CARN, Vol. 42, Issue. 1)

The cloud will change everything (CARN, Vol. 39, Issue. 1)

DoublePlay:parallelizing sequential logging and replay (CARN, Vol. 39, Issue. 1)

Pocket cloudlets (CARN, Vol. 39, Issue. 1)

Specifying and checking semantic atomicity for multithreaded programs (CARN, Vol. 39, Issue. 1)

Ensuring operating system kernel integrity with OSck (CARN, Vol. 39, Issue. 1)

Synthesizing concurrent schedulers for irregular algorithms (CARN, Vol. 39, Issue. 1)

Similar Documents

Synthesizing concurrent schedulers for irregular algorithms (SIGP, Vol. 46, Issue. 3)

Synthesizing concurrent schedulers for irregular algorithms

A case for neuromorphic ISAs (CARN, Vol. 39, Issue. 1)

Deterministic galois:on-demand, portable and parameterless (CARN, Vol. 42, Issue. 1)

The cloud will change everything (CARN, Vol. 39, Issue. 1)

DoublePlay:parallelizing sequential logging and replay (CARN, Vol. 39, Issue. 1)

Pocket cloudlets (CARN, Vol. 39, Issue. 1)

Specifying and checking semantic atomicity for multithreaded programs (CARN, Vol. 39, Issue. 1)

Ensuring operating system kernel integrity with OSck (CARN, Vol. 39, Issue. 1)

Synthesizing concurrent schedulers for irregular algorithms (CARN, Vol. 39, Issue. 1)