A priority assignment strategy of processing elements over an on-chip bus
Pages 1176 - 1180
Abstract
The number of bus transactions in System-on-Chip (SoC) grows significantly in recent years. Because of different timing constraints for different applications, how to find a proper priority assignment for processing elements (PEs) of SoC becomes very challenging. In this paper, we first show that the priority assignment problem with one unique priority for each PE is NP-complete. When each bus transaction can have one unique priority, we propose an optimal priority assignment algorithm for a given workload. We then propose a priority assignment strategy based on Simulated Annealing (SA) for PEs, where bus arbitration is done in a priority-driven fashion. The objective is to minimize the number of priorities needed for each PE and to satisfy the timing constraints of applications. The experimental results show some encouraging results in priority assignment.
References
[1]
Amba 2.0 specification. http://www.arm.com.
[2]
Coreconnect bus architecture. http://www.ibm.com.
[3]
Jin-soo kim. http://www.freepatentsonline.com/6810456.html.
[4]
L. Benini and G. D. Micheli. Networks on chips: A new soc paradigm. IEEE Computer, pages 70--80, 2002.
[5]
T. Givargis and F. Vahid. Platune: a tuning framework for system-on-a-chip platforms. IEEE Trans. on CAD of Integrated Circuits and Systems, 21(11):1317--1327, 2002.
[6]
K. Kettler, J. Lehoczky, and J. Strosnider. Modeling bus scheduling policies for real-time systems. Proceedings of the IEEE Real-Time Systems Symposium, pages 242--255, 1995.
[7]
S. Kumar, A. Jantsch, J.-P. Soininen, M. Forsell, M. Millberg, J. Oberg, K. Tiensyrja, and A. Hemani. A network on chip architecture and design methodology. Proceedings of the IEEE Computer Society Annual Symposium on VLSI, 2002.
[8]
J. Lehoczky and L. Sha. Performance of real-time bus scheduling algorithms. ACM Performance Evaluation Review, 14, 1986.
[9]
C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM, 20(1):46--61, 1973.
[10]
A. K. Mok. The design of real-time programming systems based on process models. In Proceedings of the 1984 Real Time Systems Symposium, pages 5--17, 1984.
[11]
P. Richard. On the complexity of scheduling real-time tasks with self-suspensions on one processor. Proceedings of the 15th Euromicro Conference on Real-Time Systems (ECRTS'03), pages 187--194, 2003.
[12]
J.-B. Rigaud, L. Fesquet, M. Renaudin, and J. Quartana:. High-level modeling and design of asynchronous arbiters for on-chip communication systems. DATE2002, 1090, 2002.
[13]
R. P. Dick, R. D. L, and W. Wolf. TGFF: Task graphs for free. In Workshop Hardware/Software Codesign, Mar 1998.
[14]
T. Seceleanu, V. Leppanen, J. Suomi, and O. Nevalainen. Resource allocation methodology for the segmented bus platform. In Proceedings of IEEE SOC Conference, pages 129--132, 2005.
[15]
C. Shin, Y.-T. Kim, E.-Y. Chung, K.-M. Choi, J.-T. Kong, and S.-K. Eo. Fast exploration of parameterized bus architecture for communication-centric soc design. In DATE, pages 352--357, 2004.
[16]
S. Srinivasan, F. Angiolini, M. Ruggiero, L. Benini, and N. Vijaykrishnan. Simultaneous memory and bus partitioning for soc architectures. In Proceedings of SOC Conference, 2005., pages 125--128, 2005.
[17]
P. Wielage and K. Goossens. Networks on silicon: Blessing or nightmare? Euromicro Symposium on Digital System Design, pages 196--200, 2002.
[18]
W. Wolf. A decade of hardware/software codesign. Proceedings of the IEEE Computer Society, 36:38--43, 2003.
[19]
T.-Y. Yen and W. Wolf. Performance estimation for real-time distributed embedded systems. IEEE Transactions on Parallel and Distributed Systems, 9(11), Nomeber 1998.
[20]
C. Zhang, W. Chan, and M. Bachtiar. Token ring arbitration circuits for dynamic priority algorithms. Proceedings of the 37th Midwest Symposium on Circuits and Systems, 1:74--77, 1994.
Index Terms
- A priority assignment strategy of processing elements over an on-chip bus
Recommendations
Semaphore Queue Priority Assignment for Real-Time Multiprocessor Synchronization
Prior work on real-time scheduling with global shared resources in multiprocessor systems assigns as much blocking as possible to the lowest-priority tasks. In this paper, we show that better schedulability can be achieved if global blocking is ...
A review of priority assignment in real-time systems
It is over 40 years since the first seminal work on priority assignment for real-time systems using fixed priority scheduling. Since then, huge progress has been made in the field of real-time scheduling with more complex models and schedulability ...
Preemptive Priority Assignment in Multichannel Systems
Customers of different priorities arrive at a system in accordance with a Poisson process. The customers are serviced by c service stations using a preemptive priority discipline. When the servicing times are exponentially distributed, this paper ...
Comments
Information & Contributors
Information
Published In
March 2007
1688 pages
ISBN:1595934804
DOI:10.1145/1244002
- Conference Chairs:
- Yookun Cho,
- Roger L. Wainwright,
- Hisham M. Haddad,
- Sung Y. Shin,
- Program Chair:
- Yong Wan Koo
Copyright © 2007 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 March 2007
Check for updates
Author Tags
Qualifiers
- Article
Conference
SAC07
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,650 of 6,669 submissions, 25%
Upcoming Conference
SAC '25
- Sponsor:
- sigapp
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 148Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in