Towards The Design And Optimization Of Real-time Systems On Networks-on-chip

Since a further increase in the clock frequency of current single-core processors would lead to significant power consumption and serious heating problems,chip vendors and academic researchers have moved to the development of multi-core platforms including multiple cores with lower frequencies and voltages.Meanwhile,the communication backbone of multi-core processors must scale with the number of cores for communication,synchronization,and memory access.Otherwise,the computation capability of multi-core processors would not be fully utilized and thus wasted.One prevalent solution of communication backbone is the network-on-chip(No C)architecture due to the good scalability and high communication efficiency,in which parallel inter-core communication is allowed with moderate hardware cost.Due to the high-performance requirement of real-time parallel applications(e.g.,robotics,avionics,and autonomous vehicles),the platforms of No C-based multi-core processors with high parallel processing capability are widely utilized.For real-time applications that are mapped on such platforms,the real-time guarantee is an essential requirement,i.e.,besides the logical requirement,the temporal deadline requirement should also be met.Although the No C-based multi-core platforms are considerably powerful to execute real-time applications,the software based on that is not fully supported commensurately.One of the main challenges of No C-based multi-core real-time systems is to estimate the response time upper bounds in the design-time schedulability tests,which is related to both the underlying No C architecture and the corresponding scheduling policy.The unsolved problems in the state-of-the-art(SOTA)works are as follows.First,a bottleneck has been reached in the SOTA real-time analysis on widely-used priority-preemptive wormhole No Cs due to the architecture limitation of traditional hop-by-hop traversal No Cs.Specifically,there is a chance for hard real-time applications that deadlines would be violated even under the zero-load conditions,especially for a packet flow with a long-distance route and tight deadline.And they did not consider the priority/VCs share and the generally arbitrary-deadline packet flow model,which limit the application range.Second,the widely-used dynamic scheduler on multi-core systems would suffer timing anomalies,meaning that the actual response time at runtime can be longer than the design-time estimated response time bound that is derived by assuming the jobs are executed for their WCETs,which leads to bound unsafety and unschedulability.Third,the widely-used No Cs(e.g.,wormhole No Cs)are generally designed for best-effort traffics and average-case performance,thus demonstrating poor quality on bounds estimation(i.e.,either unsafe or pessimistic).Fourth,all of the SOTA works unilaterally consider the computation tasks or communication packet flows.Such assumption is not practical in many situations,which limits the application range of the developed scheduling approaches and corresponding real-time analysis models.To address the aforementioned unsolved problems and challenges,this thesis has proposed new scheduling strategies and the matched real-time analysis models to derive safe and tight response time bounds in the following three aspects: build real-time analysis on a new No C architecture,develop safely dynamic task scheduling approach on multi-core platforms,and conduct joint real-time analysis by considering the computation and communication workloads on No C-based multi-cores.Compared with the SOTA works,this work significantly improves the real-time performance of No C-based multi-core systems through the new No C architecture,new scheduling strategies,and new response time analysis models.Specifically,the main contributions of this thesis are as follows:(1)This thesis introduces a new kind of single-cycle multi-hop traversal No C,called SMART,to reduce the worst-case traversal latency.To make SMART latency-predictable,combined with the single-cycle bypass forwarding techniques,this thesis proposes a priority-preemptive scheduling approach to allow contending packets to be arbitrated according to the predefined priorities.Based on the priority-based scheduling scheme,this thesis then proposes corresponding real-time communication analysis models by considering shared virtual channels(or priority levels)and the generally arbitrary-deadline packet flow models to estimate worst-case traversal latency and validate schedulability for the packet flows with given flow mapping and priorities.(2)This thesis proposes a timing-anomaly-free dynamic scheduler to derive safe and tight response time bounds for real-time DAG tasks on multi-core platforms.The main idea is to eliminate the timing anomaly in scheduling DAG tasks by enforcing certain order constraints among the vertices,and thus the bounds can be safely predicted by “simulating” the runtime scheduling.A key challenge to apply the timing-anomaly free scheduling approach to conditional DAG tasks is that at runtime it may generate exponential execution instances.To deal with this problem,this thesis develops effective abstractions,based on which safe bounds are computed in polynomial time.Finally,this thesis proposes an algorithm to explore the vertex orders to shorten the bounds.(3)This thesis presents an order-based scheduling paradigm,called DAG-Order,to guarantee No C real-time services by finely considering computation and communication workloads simultaneously.Rather than build the new analysis to fit the widely-used wormhole No Cs,DAG-Order is built upon another kind of advanced low-latency single-cycle long-range traversal No C(called SLT No C)to avoid the unpredictable parallel transmission on a single source-destination long-range link.To make SLT No C timing-predictable,DAG-Order achieves provably bound safety by enforcing certain order constraints among DAG vertices/edges that eliminate timing anomaly,and the order constraints are further relaxed later for higher average-case runtime performance without compromising the bound safety.Finally,to tighten the response time bounds,an effective heuristic algorithm for exploring a proper schedule order is proposed.Comprehensive experiments are conducted on synthetic and realistic benchmarks.Experimental results demonstrate the real-time performance improvement of the proposed suite of scheduling approaches and corresponding response time analysis models in terms of the bound tightness and average-case runtime performance.