NDLI: Fast Crown Scheduling Heuristics for Energy-Efficient Mapping and Scaling of Moldable Streaming Tasks on Manycore Systems

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

ACM Transactions on Architecture and Code Optimization (TACO) : Volume 13

ACM Transactions on Architecture and Code Optimization (TACO) : Volume 12

ACM Transactions on Architecture and Code Optimization (TACO) : Volume 11

Issue 4, January 2015

Bones: An Automatic Skeleton-Based C-to-CUDA Compiler for GPUs

Building and Optimizing MRAM-Based Commodity Memories

Revisiting the Complexity of Hardware Cache Coherence and Some Implications

Volatile STT-RAM Scratchpad Design and Data Allocation for Low Energy

Topological Characterization of Hamming and Dragonfly Networks and Its Implications on Routing

Efficient Data Mapping and Buffering Techniques for Multilevel Cell Phase-Change Memories

Efficient Out-of-Order Execution of Guarded ISAs

Automatic and Portable Mapping of Data Parallel Programs to OpenCL for GPU-Based Heterogeneous Systems

Improving Hybrid FTL by Fully Exploiting Internal SSD Parallelism with Virtual Blocks

MAPS: Optimizing Massively Parallel Applications Using Device-Level Memory Abstraction

Improving Multibank Memory Access Parallelism with Lattice-Based Partitioning

The Effects of Parameter Tuning in Software Thread-Level Speculation in JavaScript Engines

Studying Optimal Spilling in the Light of SSA

Compiler-Directed Power Management for Superscalars

Efficient Data Encoding for Convolutional Neural Network application

Mechanistic Analytical Modeling of Superscalar In-Order Processor Performance

Mitigating Prefetcher-Caused Pollution Using Informed Caching Policies for Prefetched Blocks

Architectural Support for Data-Driven Execution

GP-SIMD Processing-in-Memory

The Impact of the SIMD Width on Control-Flow and Memory Divergence

Measuring Microarchitectural Details of Multi- and Many-Core Memory Systems through Microbenchmarking

Low-Power High-Efficiency Video Decoding using General-Purpose Processors

Cross-Loop Optimization of Arithmetic Intensity for Finite Element Local Assembly

Optimal Parallelogram Selection for Hierarchical Tiling

Making the Most of SMT in HPC: System- and Application-Level Perspectives

Optimizing Memory Translation Emulation in Full System Emulators

Compiler/Runtime Framework for Dynamic Dataflow Parallelization of Tiled Programs

Fast Crown Scheduling Heuristics for Energy-Efficient Mapping and Scaling of Moldable Streaming Tasks on Manycore Systems

Transactional Read-Modify-Write Without Aborts

Using Template Matching to Infer Parallel Design Patterns

Efficient Correction of Anomalies in Snapshot Isolation Transactions

Perfect Reconstructability of Control Flow from Demand Dependence Graphs

On Using the Roofline Model with Lower Bounds on Data Movement

List of Distinguished Reviewers ACM TACO 2014

Issue 3, October 2014

Issue 2, June 2014

Issue 1, February 2014

ACM Transactions on Architecture and Code Optimization (TACO) : Volume 10

ACM Transactions on Architecture and Code Optimization (TACO) : Volume 9

ACM Transactions on Architecture and Code Optimization (TACO) : Volume 8

ACM Transactions on Architecture and Code Optimization (TACO) : Volume 7

ACM Transactions on Architecture and Code Optimization (TACO) : Volume 6

ACM Transactions on Architecture and Code Optimization (TACO) : Volume 5

ACM Transactions on Architecture and Code Optimization (TACO) : Volume 4

ACM Transactions on Architecture and Code Optimization (TACO) : Volume 3

ACM Transactions on Architecture and Code Optimization (TACO) : Volume 2

ACM Transactions on Architecture and Code Optimization (TACO) : Volume 1

Fast Crown Scheduling Heuristics for Energy-Efficient Mapping and Scaling of Moldable Streaming Tasks on Manycore Systems

Content Provider	ACM Digital Library
Author	Kessler, Christoph Eitschberger, Patrick Melot, Nicolas Keller, Jörg
Copyright Year	2015
Abstract	Exploiting effectively massively parallel architectures is a major challenge that stream programming can help facilitate. We investigate the problem of generating energy-optimal code for a collection of streaming tasks that include parallelizable or moldable tasks on a generic manycore processor with dynamic discrete frequency scaling. Streaming task collections differ from classical task sets in that all tasks are running concurrently, so that cores typically run several tasks that are scheduled round-robin at user level in a data-driven way. A stream of data flows through the tasks and intermediate results may be forwarded to other tasks, as in a pipelined task graph. In this article, we consider crown scheduling, a novel technique for the combined optimization of resource allocation, mapping, and discrete voltage/frequency scaling for moldable streaming task collections in order to optimize energy efficiency given a throughput constraint. We first present optimal offline algorithms for separate and integrated crown scheduling based on integer linear programming (ILP). We make no restricting assumption about speedup behavior. We introduce the fast heuristic Longest Task, Lowest Group (LTLG) as a generalization of the Longest Processing Time (LPT) algorithm to achieve a load-balanced mapping of parallel tasks, and the $\textit{Height}$ heuristic for crown frequency scaling. We use them in feedback loop heuristics based on binary search and simulated annealing to optimize crown allocation. Our experimental evaluation of the ILP models for a generic manycore architecture shows that at least for small and medium-sized streaming task collections even the integrated variant of crown scheduling can be solved to optimality by a state-of-the-art ILP solver within a few seconds. Our heuristics produce makespan and energy consumption close to optimality within the limits of the phase-separated crown scheduling technique and the crown structure. Their optimization time is longer than the one of other algorithms we test, but our heuristics consistently produce better solutions.
Starting Page	1
Ending Page	24
Page Count	24
File Format	PDF
ISSN	15443566
e-ISSN	15443973
DOI	10.1145/2687653
Volume Number	11
Issue Number	4
Journal	ACM Transactions on Architecture and Code Optimization (TACO)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-01-09
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Multicore Frequency scaling Manycore Mapping Parallel energy Scheduling Streaming
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems 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

Fast Crown Scheduling Heuristics for Energy-Efficient Mapping and Scaling of Moldable Streaming Tasks on Many-Core Systems

Energy-Efficient Scheduling of Periodic Real-Time Tasks on Lightly Loaded Multicore Processors

Static and Dynamic Frequency Scaling on Multicore CPUs

Energy-Efficient Task Scheduling in Manycore Processors with Frequency Scaling Overhead

Run-Time Management for Multicore Embedded Systems With Energy Harvesting

Energy- and performance-aware scheduling of tasks on parallel and distributed systems

Crown scheduling: energy-efficient resource allocation, mapping and discrete frequency scaling for collections of malleable streaming tasks.

Energy-efficient tasks scheduling algorithm for real-time multiprocessor embedded systems

Minimizing Cost of Scheduling Tasks on Heterogeneous Multicore Embedded Systems

Fast Crown Scheduling Heuristics for Energy-Efficient Mapping and Scaling of Moldable Streaming Tasks on Manycore Systems

Similar Documents

Fast Crown Scheduling Heuristics for Energy-Efficient Mapping and Scaling of Moldable Streaming Tasks on Many-Core Systems

Energy-Efficient Scheduling of Periodic Real-Time Tasks on Lightly Loaded Multicore Processors

Static and Dynamic Frequency Scaling on Multicore CPUs

Energy-Efficient Task Scheduling in Manycore Processors with Frequency Scaling Overhead

Run-Time Management for Multicore Embedded Systems With Energy Harvesting

Energy- and performance-aware scheduling of tasks on parallel and distributed systems

Crown scheduling: energy-efficient resource allocation, mapping and discrete frequency scaling for collections of malleable streaming tasks.

Energy-efficient tasks scheduling algorithm for real-time multiprocessor embedded systems

Minimizing Cost of Scheduling Tasks on Heterogeneous Multicore Embedded Systems

Fast Crown Scheduling Heuristics for Energy-Efficient Mapping and Scaling of Moldable Streaming Tasks on Manycore Systems