Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Optimization of task allocation and priority assignment in hard real-time distributed systems
Zhu Q., Zeng H., Zheng W., Di Natale M., Sangiovanni-Vincentelli A. ACM Transactions on Embedded Computing Systems11 (4):1-30,2012.Type:Article
Date Reviewed: Apr 29 2013

Zhu et al. study the problem of assigning tasks and signals in an automotive environment, specifically, a vehicle consisting of sensors, actuators, and processors (engine control units, or ECUs) connected by buses. The problem is to map a set of tasks to the ECUs and map signals to message frames on the buses to meet hard real-time constraints on the response to certain events. The goal is to reduce latency in responding to events in general.

This paper will be of interest to readers on multiple fronts. First, given the prevalence of distributed computing in automobiles today, many readers will appreciate this glimpse into how information processing happens in vehicles. Second, for uninitiated readers like me, the authors provide some insight into how task assignment can be formulated as a mixed integer linear programming (MILP) problem. While the text is (naturally) heavy on mathematics and thus hard to follow, there are nevertheless some clear markers that allow even the casual reader to figure out what is going on. Although I have little expertise in the application area, it does appear to me that the authors have applied their MILP formulation to an industrial-strength problem, taking five hours to solve a system with upwards of 30,000 variables. They have taken practical steps to increase the tractability of the problem by splitting it into two parts that are assumed to be independent. The solution is much better than stochastic approaches, such as simulated annealing, which takes 23 hours to converge to the same result.

Finally, from the perspective of someone with a performance modeling background, the choice of minimizing the sum of latencies as the objective function (equation 70) seems to me to be an interesting approach. I had implicitly assumed that the MILP formulation was chosen purely to meet hard deadlines, but optimizing the sum of latencies using task assignment is an interesting way to approach performance. On the performance front, however, I wish the authors had provided a slightly more complete treatment of queueing delays beyond blocking and (worst-case) interference. It seems to me that this issue causes the solution to be biased toward focusing only on hard real-time deadlines.

Reviewer:  Amitabha Roy Review #: CR141184 (1307-0626)
Bookmark and Share
 
Special-Purpose And Application-Based Systems (C.3 )
 
 
Optimization (G.1.6 )
 
Would you recommend this review?
yes
no
Other reviews under "Special-Purpose And Application-Based Systems": Date
Amortized analyses of self-organizing sequential search heuristics
Bentley J., McGeoch C. Communications of the ACM 28(4): 404-411, 1985. Type: Article
Sep 1 1985
Intelligent instrumentation
Barney G. (ed), Prentice-Hall, Inc., Upper Saddle River, NJ, 1985. Type: Book (9789780134689432)
Jul 1 1986
Programmable digital waveform generator
Smith R. Microprocessors & Microsystems 13(3): 149-158, 1989. Type: Article
Feb 1 1990
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy