The Computer Journal Advance Access published online on September 11, 2009
The Computer Journal, doi:10.1093/comjnl/bxp084
Task Allocation and Optimization of Distributed Embedded Systems with Simulated Annealing and Geometric Programming
1 Deptartment of Computer Science and Engineering, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong, China
2 College of Computer Science, Zhejiang University, Hangzhou, Zhejiang Province, China
3 School of Microelectronics, Shanghai Jiao Tong University, Shanghai 200240, China
* Corresponding author: zonghua{at}gmail.com
Received 20 March 2009; revised 12 August 2009
We consider the task model of periodic tasks running on a network of processor nodes connected by a bus based on the time-triggered protocol, an industry-standard bus protocol designed for safety-critical automotive and avionics distributed embedded systems, and present an integrated optimization framework that jointly considers one or more of the following attributes: task-to-processor allocation, task priority assignment, task period assignment and bus access configuration. We adopt a hierarchical optimization framework, where each possible task allocation and priority assignment is treated as one top-level coarse-grained state, which may contain many lower-level fine-grained states defined by different task period assignments and bus access configurations. Simulated annealing is used to explore the top-level states, which calls a geometric programming solver as a subroutine to explore the lower-level states contained within a given top-level state. Performance evaluation shows that our framework has good performance in terms of solution quality and scalability.
Key Words: real-time • embedded • scheduling