×

zbMATH — the first resource for mathematics

Processing element allocation and dynamic scheduling codesign for multi-function SoCs. (English) Zbl 1186.68081
Summary: This work is motivated by the rapid increase in design complexity of many multi-function System on Chips. It proposes solutions to both resolve the hardware contention issues of non-preemptive processing elements shared among tasks, and to optimize cost. A software solution based on start time management is proposed to interleave task execution on processing elements. Algorithms are proposed to determine the required processing elements of selected types, when there is no knowledge on the release time of any task. For tasks whose release orders are known a priori, an optimal algorithm is presented if processing elements have the same cost, otherwise, if processing elements do not have the same cost, a pseudo polynomial-time algorithm based on dynamic programming is presented. The performance of the algorithms is also evaluated for general cases.
MSC:
68M99 Computer system organization
Software:
TGFF
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aldowaisan T, Allahverdi A (2003) New heuristics for no-wait flowshops to minimize makespan. Comput Oper Res 30(8) · Zbl 1047.90053
[2] Benini L, Bertozzi D, Guerri A, Milano M (2006) Allocation, scheduling and voltage scaling on energy aware MPSoCs. In: International conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems · Zbl 1177.68023
[3] Chen Y-S, Change L-P, Kuo T-W, Mok AK (2009) An anomaly prevention approach for real-time task scheduling. J Syst Softw 82(1)
[4] Cho Y, Lee G, Yoo S, Choi K, Zergainoh N-E (2003) Scheduling and timing analysis of hw/sw on-chip communication in MP SoC design. In: International conference on design, automation and test in Europe
[5] Cho Y, Yoo S, Choi K, Zergainoh N-E, Jerraya AA (2005) Scheduler implementation in MP SoC design. In: International conference on Asia south pacific design automation
[6] Chou PH, Ortega RB, Borriello G (1995) The Chinook hardware/software co-synthesis system. In: International symposium on system synthesis
[7] Cloutier RJ, Thomas DE (1991) The combination of scheduling, allocation, and mapping in a single algorithm. In: International conference on design automation
[8] Cormen TH, Leiserson CE, Rivest RL, Stein C (1979) Introduction to algorithms. MIT Press, Cambridge
[9] Dave BP, Lakshminarayana G, Jha NK (1997) Cosyn: Hardware-software co-synthesis of embedded systems. In: International conference on design automation
[10] Dick R, Rhondes D, Wolf W (1998) TGFF: Task graphs for free. In: International workshop hardware/software codesign
[11] Dolby Inc. (2006) AC3 5.1 channel production guideline. Technical report, Dolby, http://www.dolby.com/resources/tech_library
[12] Dolif E, Lombardi M, Ruggiero M, Milano M, Benini L (2007) Communication-aware stochastic allocation and scheduling framework for conditional task graphs in multi-processor systems-on-chip. In: International conference on embedded software
[13] Eles P, Kuchcinski K, Peng Z, Doboli A, Pop P (1998) Scheduling of conditional process graphs for the synthesis of embedded systems. In: International conference on design, automation and test in Europe
[14] Eles P, Izosimov V, Pop P, Peng Z (2008) Synthesis of fault-tolerant embedded systems. In: International conference on design, automation, and test in Europe
[15] Ernst R, Henkel J, Bennr T (1993) Hardware-software cosynthesis for microcontrollers. IEEE Des Test Comput 10(4)
[16] Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W H Freeman, San Francisco · Zbl 0411.68039
[17] Goyal SK, Sriskandarajah C (1998) No-wait shop scheduling: computational complexity and approximate algorithms. Oper Res 25(4) · Zbl 0661.90045
[18] Gu Z, Zhu C, Shang L, Dick RP (2008) Application-specific MPSoC reliability optimization. IEEE Trans VLSI Syst 16(5)
[19] Gupta RK, Micheli GD (1993) Hardware-software cosynthesis for digital systems. In: International conference on design and test of computers
[20] Hall NG (1996) A survey of machine scheduling problems with blocking and no-wait in process. Oper Res 44(3) · Zbl 0864.90060
[21] ITRI SoC Technical Center (2006) Parallel architecture core digital signal processor core. Technical report, Industrial Technology Research Institute, Taiwan
[22] Kalczynski PJ, Kamburowski J (2007) On no-wait and no-idle flow shops with makespan criterion. Eur J Oper Res 178(8) · Zbl 1163.90493
[23] Lee C, Potkonjak M, Wolf W (1996) System-level synthesis of application-specific systems using a* search and generalized force-directed heuristics. In: International symposium on system synthesis
[24] Leung L-F, Tsui C-Y, Ki W-H (2004) Minimizing energy consumption of multiple-processors-core systems with simultaneous task allocation, scheduling and voltage assignment. In: International conference on Asia and south pacific design automation
[25] Liu B, Wang L, Jin Y, Huang D (2005) Designing neural networks using hybrid particle swarm optimization. Lecture notes in computer science, vol 3496
[26] Liu B, Wang L, Jin Y-H (2007) An effective hybrid particle swarm optimization for no-wait flow shop scheduling. Int J Adv Manuf Technol 31(8)
[27] Maxiaguine A, Chakraborty S, KuNZLI S, Thiele L (2004) Evaluating schedulers for multimedia processing on buffer-constrained soc platforms. IEEE Des Test Comput 21(5)
[28] Mok AK (1983) Fundamental design problems of distributed systems for hard real-time environment. PhD thesis, Massachusetts Institute of Technology, Cambridge
[29] Mok AK (2000) Tracking real-time systems requirements. In: Workshop on modelling software system structures in a fastly moving scenario
[30] Murthy PK, Bhattacharyya SS (2001) Shard buffer implementations of signal processing systems using lifetime analysis techniques. IEEE Trans Comput-Aided Des Integr Circuits Syst 20(2)
[31] Oh H, Ha S (2002) Hardware-software cosynthesis of multi-mode multi-task embedded systems with real-time constraints. In: International conference on hardware/software codesign and system synthesis
[32] Oh H, Ha S (2003) Memory-optimized software synthesis from dataflow program graphs with large data samples. EURASIP J Appl Signal Process 2003(6) · Zbl 1089.68540
[33] Prabhakaran P, Banerjee P (1996) Parallel algorithms for force directed scheduling of flattened and hierarchical signal flow graphs. In: International conference on computer design
[34] Richter K, Jersak M, Ernst R (2003) A formal approach to MpSoC performance verification. Computer 36(4)
[35] Ruggieroy M, Guerri A, Bertozzi D, Poletti F, Milano M (2006) Communication aware allocation and scheduling framework for stream oriented multi-processor systems on chip. In: International conference on design, automation and test in Europe
[36] Santambrogio MD, Rana V, Memik SO, Acar UA, Sciuto D (2007) A novel soc design methodology combining adaptive software and reconfigurable hardware. In: International conference on computer aided design
[37] Shirvaikar M, Estevez DL (2002) Digital camera design with JPEG, MPEG4, MP3 and 802.11 features. In: Workshop presentation, embedded systems conference
[38] Simmler H, Levinson L, Manner R (2002) Multitasking on FPGA coprocessors. In: International conference on field programmable logic and applications
[39] Stankovic JA, Spuri M, Natale MD, Buttazzo G (1994) Implications of classical scheduling results for real-time systems. IEEE Trans Comput 28(6)
[40] Stankovic JA, Spuri M, Di Natale M, Buttazzo GC (1995) Implications of classical scheduling results for real-time systems. Computer 28(6)
[41] Texas Instruments Inc. (2006) OMAP platform. Technical report, Texas Instruments, http://focus.ti.com/omap/docs/omaphomepage.tsp
[42] Thornton HW, Hunsucker JL (2004) A new heuristic for minimal makespan in flow shops with multiple processors and no intermediate storage. Eur J Oper Res 152(1) · Zbl 1043.90034
[43] Walder H, Platzner M (2003) Reconfigurable hardware OS prototype. Technical report, Swiss Federal Institute of Technology, http://citeseer.ist.psu.edu/walder03reconfigurable.html
[44] Xie Y, Wolf W (2000) Co-synthesis with custom asics. In: International conference on Asia and south pacific design automation
[45] Xie Y, Wolf W (2001) Allocation and scheduling of conditionals task graph in hardware software co-synthesis. In: International conference on design, automation, and test in Europe
[46] Zhu C, Gu Z, Dick RP, Shang L (2007) Reliable multiprocessor system-on-chip synthesis. In: International conference on hardware software codesign
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.