Title: Hardware-software architecture for priority queue management in real-time and embedded systems

Authors: N.G. Chetan Kumar; Sudhanshu Vyas; Ron K. Cytron; Christopher D. Gill; Joseph Zambreno; Phillip H. Jones

Addresses: Department of Electrical and Computer Engineering, Iowa State University, 2215 Coover Hall, Ames, IA 50011, USA ' Department of Electrical and Computer Engineering, Iowa State University, 2215 Coover Hall, Ames, IA 50011, USA ' Department of Computer Science and Engineering, Washington University in St. Louis, 1 Brookings Dr., St. Louis, MO 63130, USA ' Department of Computer Science and Engineering, Washington University in St. Louis, 1 Brookings Dr., St. Louis, MO 63130, USA ' Department of Electrical and Computer Engineering, Iowa State University, 2215 Coover Hall, Ames, IA 50011, USA ' Department of Electrical and Computer Engineering, Iowa State University, 2215 Coover Hall, Ames, IA 50011, USA

Abstract: The use of hardware-based data structures for accelerating real-time and embedded system applications is limited by the scarceness of hardware resources. Being limited by the silicon area available, hardware data structures cannot scale in size as easily as their software counterparts. We assert a hardware-software co-design approach is required to elegantly overcome these limitations. In this paper, we present a hybrid priority queue architecture that includes a hardware accelerated binary heap that can also be managed in software when the queue size exceeds hardware limits. A memory mapped interface provides software with access to priority-queue structured on-chip memory, which enables quick and low overhead transitions between hardware and software management. As an application of this hybrid architecture, we present a scalable task scheduler for real-time systems that reduces scheduler processing overhead and improves timing determinism of the scheduler.

Keywords: priority queues; hardware-software co-design; real-time systems; embedded systems; hardware scheduling; hardware accelerated binary heap; memory mapped interface; hardware mangement; software management.

DOI: 10.1504/IJES.2014.064997

International Journal of Embedded Systems, 2014 Vol.6 No.4, pp.319 - 334

Received: 08 Apr 2013
Accepted: 18 Dec 2013

Published online: 11 Oct 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article