Hardware/software partitioning of operating systems: focus on deadlock detection and avoidance
Hardware/software partitioning of operating systems: focus on deadlock detection and avoidance
- Author(s): J.J. Lee and V.J. Mooney
- DOI: 10.1049/ip-cdt:20045078
For access to this article, please select a purchase option:
Buy article PDF
Buy Knowledge Pack
IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.
Thank you
Your recommendation has been sent to your librarian.
- Author(s): J.J. Lee 1 and V.J. Mooney 1
-
-
View affiliations
-
Affiliations:
1: Center for Research on Embedded Systems and Technology, Georgia Institute of Technology, Atlanta, USA
-
Affiliations:
1: Center for Research on Embedded Systems and Technology, Georgia Institute of Technology, Atlanta, USA
- Source:
Volume 152, Issue 2,
March 2005,
p.
167 – 182
DOI: 10.1049/ip-cdt:20045078 , Print ISSN 1350-2387, Online ISSN 1359-7027
As multiprocessor system-on-a-chip (MPSoC) designs become more common, hardware/software codesign engineers face new challenges involving operating system integration. To speed up operating system/MPSoC codesign, the paper presents recent research in hardware/software partitioning of a real-time operating system (RTOS). After a brief overview of the δ hardware/software RTOS design framework, the authors focus on new results in deadlock detection and avoidance. Among various configured RTOS/MPSoC designs in this research, they show an example where a system with the deadlock detection hardware unit (DDU) achieves a 46% speed-up of application execution time over a system with deadlock detection in software. Similarly, they show another example where a system with the deadlock avoidance hardware unit (DAU) not only automatically avoids deadlock but also achieves a 44% speed-up of application execution time over a system avoiding deadlock in software; furthermore, in our example, the DAU only consumes 0.005% of the MPSoC total chip area.
Inspec keywords: real-time systems; concurrency control; hardware-software codesign; operating systems (computers); system-on-chip; multiprocessing systems
Other keywords:
Subjects: Hardware-software codesign; Multiprocessing systems; Electronic engineering computing; Software engineering techniques; Digital circuit design, modelling and testing; Operating systems
References
-
-
1)
- Kim, J., Koh, K.: `An O(1) time deadlock detection scheme in single unit and single request multiprocess system', IEEE TENCON'91, 1991, 2, p. 219–223.
-
2)
- Lee, J., Ryu, K., Mooney, V.: `A framework for automatic generation of configuration files for a custom RTOS', Proc. Int. Conf. on Engineering of Reconfigurable Systems and Algorithms (ERSA), June 2002, p. 31–37.
-
3)
- Sun, D., Blough, D., Mooney, V.: `Atlanta: A new multiprocessor RTOS kernel for system-on-a-chip applications', GIT-CC-02.19, Tech., 2002, http://www.coc.gatech.edu/research/pubs.html.
-
4)
- Dijkstra, E.: `Cooperating sequential processes', EWD-123, Tech., Sep. 1965.
-
5)
- The Free Software Foundation, The GNU project, the GNU C library. http://www.gnu.org/software/libc/manual/.
-
6)
- Akgul, B., Mooney, V.: `PARLAK: Parametrized lock cache generator', Proc. Conf. on Design Automation and Test in Europe (DATE), March 2003, p. 1138–1139.
-
7)
- Woo, S., Ohara, M., Torrie, E., Singh, J., Gupta, A.: `The SPLASH-2 programs: characterization and methodological considerations', Proc. 22nd Int. Symp. on Computer Architecture, June 1995, p. 24–36.
-
8)
- Shoshani, A., Coffman, E.: `Detection, prevention and recovery from deadlocks in multiprocess, multiple resource systems', 4th Annual Princeton Conf. on Information Sciences and System, March 1970.
-
9)
- B. Akgul , V. Mooney . The system-on-a-chip lock cache. Des. Autom. Embedded Syst. , 139 - 174
-
10)
- T. Leibfried . A deadlock detection and recovery algorithm using the formalism of a directed graph matrix. Oper. Syst. Rev. , 2 , 45 - 55
-
11)
- QualCore Logic. http://www.qualcorelogic.com/.
-
12)
- Lee, J., Mooney, V., Daleby, A., Ingstrom, K., Klevin, T., Lindh, L.: `A comparison of the RTU hardware RTOS with a hardware/software RTOS', Proc. Asia and South Pacific Design Automation Conference (ASPDAC), Jan. 2003, p. 683–688.
-
13)
- Synopsys, VCS™ Verilog Simulator, http://www.synopsys.com/products/simulation/simulation.html.
-
14)
- Mentor Graphics, Hardware/Software Co-Verification: Seamless, http://www.mentor.com/seamless/.
-
15)
- Xilinx, http://www.xilinx.com/.
-
16)
- Ryu, K., Mooney, V.: `Automated bus generation for multiprocessor SoC Design', Proc. Conf. on Design Automation and Test in Europe (DATE), March 2003, p. 282–287.
-
17)
- N. Gebraeel , M. Lawley . Deadlock detection, prevention and avoidance for automated tool sharing systems. IEEE Trans. Robot. Autom. , 3 , 342 - 356
-
18)
- Shiu, P., Tan, Y., Mooney, V.: `A novel parallel deadlock detection algorithm and architecture', Proc.9th Int. Symp. on Hardware/Software Codesign (CODES'01), April 2001, p. 30–36.
-
19)
- Ryu, K.: `Automatic generation of bus systems', Summer 2004, Ph.D. Thesis, Georgia Institute of Technology, School of ECE.
-
20)
- AMI Semiconductor, http://www.amis.com.
-
21)
- The Free Software Foundation, The GNU project, the GCC compiler. http://gcc.gnu.org/.
-
22)
- M. Maekawa , A. Oldhoeft , R. Oldehoeft . (1987) Operating Systems - Advanced Concepts.
-
23)
- Shalan, M., Mooney, V.: `Hardware support for real-time embedded multiprocessor system-on-a-chip memory management', Proc. Tenth Int. Symp. on Hardware/Software Codesign (CODES), May 2002, p. 79–84.
-
24)
- Akgul, B., Mooney, V., Thane, H., Kuacharoen, P.: `Hardware support for priority inheritance', Proc. IEEE Real-Time Systems Symp. (RTSS), Dec 2003, p. 246–254.
-
25)
- Lee, J., Mooney, V.: `An O(min(m, n)) parallel deadlock detection algorithm', GIT-CC-03-41, Tech., Sep. 2003, http://www.coc.gatech.edu/research/pubs.html.
-
26)
- Design Compiler, http://www.synopsys.com/products/logic/logic.html.
-
27)
- Shalan, M.: `Dynamic memory management for embedded real-time multiprocessor system-on-a-chip', Fall 2003, Ph.D. Thesis, Georgia Institute of Technology, School of ECE, Atlanta, GA, USA.
-
28)
- F. Belik . An efficient deadlock avoidance technique. IEEE Trans. Comput. , 7 , 882 - 888
-
29)
- Shalan, M., Shin, E., Mooney, V.: `DX-Gt: Memory management and crossbar switch generator for multiprocessor system-on-a-chip', Proc. 11th Workshop on Synthesis and System Integration of Mixed Information technologies (SASIMI), April 2003, p. 357–364.
-
30)
- Mentor Graphics, XRAY® Debugger, http://www.mentor.com/xray/.
-
31)
- Akgul, B.: `The system-on-a-chip lock cache', Spring 2004, Ph.D. Thesis, School of CE, Georgia Institute of Technology, Atlanta, GA, USA.
-
32)
- J. Hennessy , D. Patterson . (1996) Computer architecture - a quantitative approach.
-
33)
- R. Holt . Some deadlock properties of computer systems. Comput. Surv. , 179 - 196
-
34)
- E. Coffman , M. Elphick , A. Shoshani . System deadlocks. Comput. Surv. , 2 , 67 - 78
-
35)
- V. Mooney , D. Blough . A hardware-software real-time operating system framework for SOCs. IEEE Des. Test Comput. , 6 , 44 - 51
-
36)
- S. Morgan . Jini to the rescue. IEEE Spectrum , 4 , 44 - 49
-
37)
- Stanford University, Stanford Parallel Applications for Shared Memory (SPLASH). http://www.flash.stanford.edu/apps/SPLASH/.
-
38)
- V. Mooney . (2003) Hardware/software partitioning of operating systems, Embedded software for SoC.
-
39)
- K. Ryu , V. Mooney . Automated bus generation for multiprocessor SoC design. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst.
-
40)
- Akgul, B., Lee, J., Mooney, V.: `A system-on-a-chip lock cache with task preemption support', Proc. Int. Conf. on Compilers, Architecture and Synthesis for Embedded Systems (CASES), Nov. 2001, p. 149–157.
-
41)
- L. Sha , R. Rajkumar , J. Lehoczky . Priority inheritance protocols: an approach to real-time synchronization. IEEE Trans. Comput. , 9 , 1175 - 1185
-
42)
- Lee, J., Mooney, V.: `A novel deadlock avoidance algorithm and its hardware implementation', Proc. 12th Int. Conf. on Hardware/ Software Codesign and System Synthesis (CODES/ISSS), Sep 2004, p. 200–205.
-
1)