Task Superscalar: An Out-of-Order Task Pipeline
Authors:
- Yoav EtsionYEYoav Etsion
- Felipe CabarcasFCFelipe Cabarcas
- Alejandro RicoARAlejandro Rico
- Alex RamirezARAlex Ramirez
- Rosa M. BadiaRBRosa M. Badia
- Eduard AyguadeEAEduard Ayguade
- Jesus LabartaJLJesus Labarta
- Mateo ValeroMVMateo Valero
- 1 December 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10724451,p. 89-100
Abstract
We present \emph{Task Super scalar}, an abstraction of instruction-level out-of-order pipeline that operates at the task-level. Like ILP pipelines, which uncover parallelism in a sequential instruction stream, task super scalar uncovers task-level parallelism among tasks generated by a sequential thread. Utilizing intuitive programmer annotations of task inputs and outputs, the task super scalar pipeline dynamically detects inter-task data dependencies, identifies task-level parallelism, and executes tasks out-of-order. Furthermore, we propose a design for a distributed task super scalar pipeline front end, that can be embedded into any many core fabric, and manages cores as functional units. We show that our proposed mechanism is capable of driving hundreds of cores simultaneously with non-speculative tasks, which allows our pipeline to sustain work windows consisting of tens of thousands of tasks. We further show that our pipeline can maintain a decode rate faster than 60ns per task and dynamically uncover data dependencies among as many as ~50,000 in-flight tasks, using 7MB of on-chip eDRAM storage. This configuration achieves speedups of 95-255x (average 183x) over sequential execution for nine scientific benchmarks, running on a simulated CMP with 256 cores. Task super scalar thus enables programmers to exploit many core systems effectively, while simultaneously simplifying their programming model.Keywords
This publication has 20 references indexed in Scilit:
- Dynamic task scheduling for linear algebra algorithms on distributed-memory multicore systems2009
- Available Task-Level Parallelism on the Cell BEScientific Programming, 2009
- Future Proof Data Parallel Algorithms and Software on Intel Multicore ArchitectureIntel Technology Journal, 2007
- Carbon2007
- WaveScalar2003
- StreamIt: A Language for Streaming Applications2002
- The Stanford Hydra CMPIEEE Micro, 2000
- Executing a program on the MIT tagged-token dataflow architectureIEEE Transactions on Computers, 1990
- HPS, a new microarchitecture: rationale and introduction1985
- A preliminary architecture for a basic data-flow processorACM SIGARCH Computer Architecture News, 1974