NDLI: Performance driven multi-objective distributed scheduling for parallel computations

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

Performance driven multi-objective distributed scheduling for parallel computations

Content Provider	ACM Digital Library
Author	Katta, Naga Praveen Kumar Narang, Ankur Shyamasundar, Rudrapatna K. Srivastava, Abhinav
Abstract	With the advent of many-core architectures and strong need for Petascale (and Exascale) performance in scientific domains and industry analytics, efficient scheduling of parallel computations for higher productivity and performance has become very important. Further, movement of massive amounts (Terabytes to Petabytes) of data is very expensive, which necessitates affinity driven computations. Therefore, distributed scheduling of parallel computations on multiple places 1 needs to optimize multiple performance objectives: follow affinity maximally and ensure efficient space, time and message complexity. Simultaneous consideration of these objectives makes distributed scheduling a particularly challenging problem. In addition, parallel computations have data dependent execution patterns which requires online scheduling to effectively optimize the computation orchestration as it unfolds. This paper presents an online algorithm for affinity driven distributed scheduling of multi-place 2 parallel computations. To optimize multiple performance objectives simultaneously, our algorithm uses a low time and message complexity mechanism for ensuring affinity and a randomized work-stealing mechanism within places for load balancing. Theoretical analysis of the expected and probabilistic lower and upper bounds on time and message complexity of this algorithm has been provided. On multi-core clusters such as Blue Gene/P (MPP architecture) and Intel multicore cluster, we demonstrate performance close to the custom MPI+Pthreads code. Further, strong, weak and data (increasing input data size) scalability have been demonstrated on multi-core clusters. Using well known benchmarks, we demonstrate 16% to 30% performance gain as compared to Cilk [6] on multi-core Intel Xeon 5570 (NUMA) architecture. Detailed experimental analysis illustrates efficient space (main memory) utilization as well. To the best of our knowledge, this is the first time multi-objective affinity driven distributed scheduling algorithm has been designed, theoretically analyzed and experimentally evaluated in a multi-place setup for multi-core cluster architectures.
Starting Page	14
Ending Page	27
Page Count	14
File Format	PDF
ISSN	01635980
DOI	10.1145/2007183.2007186
Journal	ACM SIGOPS Operating Systems Review (OPSR)
Volume Number	45
Issue Number	2
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1975-04-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Information Systems

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

A multi-microprocessor computer system architecture

Impact of mobility on distributed computations

Performance driven multi-objective distributed scheduling for parallel computations.

Scheduling with implicit information in distributed systems

Effective distributed scheduling of parallel workloads

Migration policies for multi-core fair-share scheduling

Understanding Parallel Performance Under Interferences in Multi-tenant Clouds

Flexibility and performance of parallel file systems

A multi-protocol cross-domain communication model for metacomputing systems

Performance driven multi-objective distributed scheduling for parallel computations

Similar Documents

A multi-microprocessor computer system architecture

Impact of mobility on distributed computations

Performance driven multi-objective distributed scheduling for parallel computations.

Scheduling with implicit information in distributed systems

Effective distributed scheduling of parallel workloads

Migration policies for multi-core fair-share scheduling

Understanding Parallel Performance Under Interferences in Multi-tenant Clouds

Flexibility and performance of parallel file systems

A multi-protocol cross-domain communication model for metacomputing systems

Performance driven multi-objective distributed scheduling for parallel computations