University of Oulu

Quasi-static scheduling for fine-grained embedded multiprocessing

Saved in:
Author: Boutellier, Jani1,2
Organizations: 1University of Oulu, Faculty of Technology, Department of Electrical and Information Engineering
2University of Oulu, Infotech Oulu
Format: ebook
Version: published version
Access: open
Online Access: PDF Full Text (PDF, 1.6 MB)
Persistent link:
Language: English
Published: 2009
Publish Date: 2009-10-27
Thesis type: Doctoral Dissertation
Defence Note: Academic dissertation to be presented with the assent of the Faculty of Technology of the University of Oulu for public defence in Auditorium TS101, Linnanmaa, on 6 November 2009, at 12 noon
Reviewer: Professor Christoph Kessler
Professor Jarmo Takala


Designing energy-efficient multiprocessing hardware for applications such as video decoding or MIMO-OFDM baseband processing is challenging because these applications require high throughput, as well as flexibility for efficient use of the processing resources. Application specific hardwired accelerator circuits are the most energy-efficient processing resources, but are inflexible by nature. Furthermore, designing an application specific circuit is expensive and time-consuming. A solution that maintains the energy-efficiency of accelerator circuits, but makes them flexible as well, is to make the accelerator circuits fine-grained.

Fine-grained application specific processing elements can be designed to implement general purpose functions that can be used in several applications and their small size makes the design and verification times reasonable. This thesis proposes an efficient method for orchestrating the use of heterogeneous fine-grained processing elements in dynamic applications without introducing tremendous orchestration overheads. Furthermore, the thesis presents a processing element management unit which performs scheduling and independent dispatching, and works with such low overheads that the use of low latency processing elements becomes worthwhile and efficient.

Dynamic orchestration of processing elements requires run-time scheduling that has to be done very fast and with as few resources as possible, for which this work proposes dividing the application into short static parts, whose schedules can be determined at system design time. This approach, often called quasi-static scheduling, captures the dynamic nature of the application, as well as minimizes the computations of run-time scheduling.

Enabling low overhead quasi-static scheduling required studying simultaneously the computational complexity and performance of simple but efficient scheduling algorithms. The requirements lead to the use of flow-shop scheduling. This thesis is the first work that adapts the flow-shop scheduling algorithms to different multiprocessor memory architectures. An extension to the flow-shop model is also presented, which enables modeling a wider scope of applications than traditional flow-shop. The feasibility of the proposed approach is demonstrated with a real multiprocessor solution that is instantiated on a field-programmable gate array.

see all

Series: Acta Universitatis Ouluensis. C, Technica
ISSN-E: 1796-2226
ISBN: 978-951-42-9272-9
ISBN Print: 978-951-42-9271-2
Issue: 342
Copyright information: © University of Oulu, 2009. This publication is copyrighted. You may download, display and print it for your own personal use. Commercial use is prohibited.