Multilayer bus optimization for real-time embedded systems

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

8 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Article number6042856
Pages (from-to)1638-1650
Journal / PublicationIEEE Transactions on Computers
Volume61
Issue number11
Online published10 Oct 2011
Publication statusPublished - Nov 2012
Externally publishedYes

Abstract

A major challenge in the design of multicore embedded systems is how to tackle the communications among tasks with performance requirements and precedence constraints. In this paper, we consider the problem of scheduling real-time tasks over multilayer bus systems with the objective of minimizing the communication cost. We show that the problem is NP-hard and determine the best possible approximation ratio of approximation algorithms. First, we propose a polynomial-time optimal algorithm for a restricted case where one multilayer bus, and the unit execution time and communication time are considered. The result is then extended as a pseudopolynomial-time optimal algorithm to consider multiple multilayer buses with arbitrary execution and communication times, as well as different timing constraints and objective functions. We compare the performance of the proposed algorithm with that of some popular heuristics, and provide further insights into the multilayer bus system design.

Research Area(s)

  • Bridges, bus cost optimization, Computer architecture, Embedded systems, Heuristic algorithms, Multilayer-bus embedded systems, precedence constraints, Program processors, Real time systems, real-time scheduling, Schedules

Citation Format(s)

Multilayer bus optimization for real-time embedded systems. / Hsiu, Pi-Cheng; Hsieh, Cheng-Kang; Lee, Der-Nien; Kuo, Tei-Wei.

In: IEEE Transactions on Computers, Vol. 61, No. 11, 6042856, 11.2012, p. 1638-1650.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review