Dai Bui and Hiren Patel and Edward A. Lee

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2009-148

October 30, 2009

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-148.pdf

Deploying real-time control systems software on multiprocessors requires distributing tasks on multiple processing elements, and coordinating their executions using a protocol. One potential protocol is the use of the discrete-event (DE) model of computation because it already defines a clear notion of the passage of time, and there is significant existing research on distributing DE. In this paper, we consider a distributed DE with null-message protocol (NMP) on a multicore system for real-time control systems. We illustrate that even with the null-message deadlock avoidance scheme in the protocol, the system may still deadlock due to inter-core message dependencies. We propose a simple analytical model to identify two central reasons for these deadlocks. They are lack of an upper bound on send and receive rates for each processing element, and an unknown upper-bound on network delay. Then, we argue that architecture features such as timing control, timing synchronization and real-time networks-on-chip can be used to prevent message-dependent deadlock. We show that we can replace NMP with a distributed DE strategy called PTIDES that helps ease the process of eliminating this deadlock problem.

---

BibTeX citation:

@techreport{Bui:EECS-2009-148,
    Author= {Bui, Dai and Patel, Hiren and Lee, Edward A.},
    Title= {On Distributed Discrete Event Execution on Chip-Multiprocessors},
    Year= {2009},
    Month= {Oct},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-148.html},
    Number= {UCB/EECS-2009-148},
    Abstract= {Deploying real-time control systems software on multiprocessors requires distributing tasks on multiple processing elements, and coordinating their executions using a protocol.  One potential protocol is the use of the discrete-event (DE) model of computation because it already defines a clear notion of the passage of time, and there is significant existing research on distributing DE. In this paper, we consider a distributed DE with null-message protocol (NMP) on a multicore system for real-time control systems. We illustrate that even with the null-message deadlock avoidance scheme in the protocol, the system may still deadlock due to inter-core message dependencies. We propose a simple analytical model to identify two central reasons for these deadlocks. They are lack of an upper bound on send and receive rates for each processing element, and an unknown upper-bound on network delay. Then, we argue that architecture features such as timing control, timing synchronization and real-time networks-on-chip can be used to prevent message-dependent deadlock. We show that we can replace NMP with a distributed DE strategy called PTIDES that helps ease the process of eliminating this deadlock problem.},
}

EndNote citation:

%0 Report
%A Bui, Dai 
%A Patel, Hiren 
%A Lee, Edward A. 
%T On Distributed Discrete Event Execution on Chip-Multiprocessors
%I EECS Department, University of California, Berkeley
%D 2009
%8 October 30
%@ UCB/EECS-2009-148
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-148.html
%F Bui:EECS-2009-148