| 221. |
- Liu, Meng, et al.
(författare)
-
Improved Priority Assignment for Real-Time Communications in On-Chip Networks
- 2015
-
Ingår i: ACM International Conference Proceeding SeriesVolume 04-06. - New York, NY, USA : ACM. - 9781450335911 ; , s. 171-180
-
Konferensbidrag (refereegranskat)abstract
- The Network-on-Chip is the on-chip interconnection medium of choice for modern massively parallel processors and System-on-Chip in general. Fixed-priority based preemptive scheduling using virtual-channels is a solution to support real-time communications in on-chip networks. However, the different characteristics of the Network-on-Chip compared to the single processor scheduling problem prevents the usage of known optimal algorithms (e.g. the Audsley's algorithm) to assign priorities to messages. A heuristic search algorithm based approach (called the HSA) focusing on the priority assignment for on-chip communications has been presented in the literature. The HSA is much faster than an exhaustive search based solution, with a price of missing certain schedulable cases (i.e. non-optimal). In this paper, we present two undirected-graph based priority assignment algorithms, the GESA and the GHSA. In contrast to the previous work, we can decrease the search space significantly by taking the interference dependencies of different messages on the network into account. A number of experiments are generated, in order to evaluate the proposed algorithms. The results show that the GESA can always achieve higher schedulability ratios than the HSA, but may require longer processing time. On the other hand, the GHSA has the same performance as the HSA regarding the schedulability, but can significantly improve the efficiency.
|
|
| 222. |
- Liu, Meng
(författare)
-
On Improving Resource Utilization in Distributed Real-Time Embedded Systems
- 2014
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In our modern life, embedded systems are playing an essential role. An embedded system is a computer system embedded into a certain device, in order to achieve computing functions. Beyond all doubt, as a validated system, the functional correctness must be guaranteed. However, for many embedded systems, timeliness also plays an important role in addition to the correctness of the functionalities. For example, in an automotive braking system, the braking function needs to be processed within a limited time duration in order to avoid accidents. Such systems are known as real-time embedded systems.In these systems, there can be plenty of software programs (called tasks) sharing limited computing resources (e.g. processors, memories). If the system executes tasks in a random way, the whole system will become unpredictable. As a result, the system designers will not be able to verify if the system design can fulfill all the timing requirements or not. In other words, the system is not guaranteed to be safe. Therefore, system designers need to carefully implement algorithms to schedule all the tasks in a predictable manner. Regarding each scheduling algorithm, schedulability analyses are proposed which are used to check if the requirements can be satisfied.Unfortunately, many real-time systems reserve too much computing resource for the sake of fulfilling timing requirements, without taking into account resource utilization. As a result, system resources cannot be efficiently utilized, which can cause significant resource waste in reality. Therefore, in this thesis, we aim to improve resource utilization in modern distributed real-time embedded systems. We try to tackle this problem from the following two aspects.Investigating tighter timing analyses. Due to the difficulty in performing precise mathematical schedulability analyses, most of the existing analyses include varying degrees of pessimism. In other words, the actual performance of the system can be much better than the predictions. If we can reduce the pessimism in schedulability analyses, we can then admit more workload into the system.Proposing new scheduling frameworks. It is difficult to find a scheduling algorithm which is suitable for all the situations. Therefore, we need different mechanisms to handle specific system characteristics in order to improve the resource utilization.
|
|
| 223. |
- Liu, Meng, et al.
(författare)
-
On providing real-time guarantees in cloud-based platforms
- 2016
-
Ingår i: IEEE International Workshop on Factory Communication Systems - Proceedings, WFCS. - 9781509023394
-
Konferensbidrag (refereegranskat)abstract
- Cloud technologies are gaining more and more attentions in recent years. Cloud-based service brings benefits in cost, energy efficiency, sharing of resources, increased flexibility, adaptability and evolvability. However, there are a number of associated challenges that need to be properly addressed before applying the cloud technique generally in industries. Providing efficient and predictable computation and communication is one of the important challenges, since many industrial systems (e.g. a control system) have specific timing requirements. Our current work thus focuses on guaranteeing the predictability of a cloud-based service. Virtualization, as one of the key technologies in Cloud Computing, is used to abstract details of resources away from end-services which simplifies the resource sharing. It thus improves the resource utilization and saves budget for end-users. In this preliminary work, we have implemented a distributed system using virtualization techniques (including virtual machines and virtual switches). Additionally, we generate a number of experiments to investigate how QoS policies can help us to provide real-time communication guarantees.
|
|
| 224. |
- Liu, Meng
(författare)
-
Real-Time Communication over Wormhole-Switched On-Chip Networks
- 2017
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In a modern industrial system, the requirement on computational capacity has increased dramatically, in order to support a higher number of functionalities, to process a larger amount of data or to make faster and safer run-time decisions. Instead of using a traditional single-core processor where threads can only be executed sequentially, multi-core and many-core processors are gaining more and more attentions nowadays. In a multi-core processor, software programs can be executed in parallel, which can thus boost the computational performance. Many-core processors are specialized multi-core processors with a larger number of cores which are designed to achieve a higher degree of parallel processing. An on-chip communication bus is a central intersection used for data-exchange between cores, memory and I/O in most multi-core processors. As the number of cores increases, more contention can occur on the communication bus which raises a bottleneck of the overall performance. Therefore, in order to reduce contention incurred on the communication bus, a many-core processor typically employs a Network-on-Chip (NoC) to achieve data-exchange. Real-time embedded systems have been widely utilized for decades. In addition to the correctness of functionalities, timeliness is also an important factor in such systems. Violation of specific timing requirements can result in performance degradation or even fatal problems. While executing real-time applications on many-core processors, the timeliness of a NoC, as a communication subsystem, is essential as well. Unfortunately, many real-time system designs over-provision resources to guarantee the fulfillment of timing requirements, which can lead to significant resource waste. For example, analysis of a NoC design yields that the network is already saturated (i.e. accepting more traffic can incur requirement violation), however, in reality the network actually has the capacity to admit more traffic. In this thesis, we target such resource wasting problems related to design and analysis of NoCs that are used in real-time systems. We propose a number of solutions to improve the schedulability of real-time traffic over wormhole-switched NoCs in order to further improve the resource utilization of the whole system. The solutions focus mainly on two aspects: (1) providing more accurate and efficient time analyses; (2) proposing more cost-effective scheduling methods.
|
|
| 225. |
- Liu, Meng, et al.
(författare)
-
Response time analysis for static priority based SpaceWire networks
- 2012
-
Ingår i: Proceeings of the 2nd International Workshop on Worst-Case Traversal Time (WCTT '12). - New York, NY, USA : ACM. - 9781450316866 ; , s. 7-14
-
Konferensbidrag (refereegranskat)abstract
- The SpaceWire network standard is used in spacecraft communications and has been selected for future ESA satellites. In order to guarantee the safety and reliability of on-board systems, the designers have to make sure that all critical timing constraints are satisfied. The SpaceWire network is a wormhole based network which makes its timing analysis significantly complex. Some methods for computing upper-bounds of end-to-end delays of certain wormhole network models have been developed. However, those models require some explicit assumptions and dedicated real-time mechanisms which cannot be supported by the current SpaceWire networks. Moreover, some work has proposed analysis approaches for SpaceWire networks assuming the Round-Robin arbitration scheme only. In this paper, we focus on the priority based arbitration scheme instead and we propose a worst-case response time analysis to evaluate the end-to-end delays of traffic transmissions in SpaceWire networks. The corresponding proofs to our analysis are presented along with a case study. © 2012 ACM.
|
|
| 226. |
- Liu, Meng, et al.
(författare)
-
Schedulability analysis of GMF-modeled messages over controller area networks with mixed-queues
- 2014
-
Ingår i: IEEE Int. Workshop Factory Commun. Syst. Proc. WFCS. - 9781479932351 ; , s. Article number 6837606-
-
Konferensbidrag (refereegranskat)abstract
- The Controller Area Network (CAN) is widely utilized in many industrial real-time applications. As a real-time communication network, the predictability of timing behaviors is very important. Therefore, many works have been proposed regarding the schedulability analysis of CAN messages. Most of the existing analysis approaches are based on a traditional periodic message model. However, in some applications, the transmission of a message may follow a certain pattern instead of repeating the same transmission period by period. In these cases, applying the existing analysis methods may lead to quite pessimistic results. In order to tackle this problem, in this paper we apply the Generalized Multi-Frame (GMF) task model on CAN messages, where both priority-based and FIFO-based message queues are taken into account. We present a corresponding sufficient schedulability analysis. According to the experimental evaluations, our analysis can provide tighter results compared to the existing CAN message response time analysis in the context of GMF-modeled messages.
|
|
| 227. |
- Liu, Meng, et al.
(författare)
-
Schedulability analysis of Multi-Frame messages over Controller Area Networks with mixed-queues
- 2013
-
Konferensbidrag (refereegranskat)abstract
- The Controller Area Network (CAN) is one of the most widely utilized real-time communication networks, which has plenty of applications especially in automotive industry. Many works have been proposed regarding the CAN schedulability analysis which is very important for guaranteeing the safety and reliability of hard real-time systems. Most of the existing analysis methods assume a periodic message model, and some of them take sporadic messages into account. However, for some applications, message transmissions may follow a specific pattern instead of repeating the same transmission period by period, where applying the existing methods may include much pessimism. In this paper, we apply the Multi-Frame task model, which is first proposed by Mok and Chen in cite{MokChen}, on CAN messages. Moreover, we assume that the ECUs in the analyzed network can employ both FIFO and priority based queues. The schedulability analysis and the corresponding proofs are provided along with a case study.
|
|
| 228. |
- Liu, Meng, et al.
(författare)
-
Scheduling Real-Time Packets with Non-preemptive Regions on Priority-Based NoCs
- 2016
-
Ingår i: Proceedings - 2016 IEEE 22nd International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2016.
-
Konferensbidrag (refereegranskat)abstract
- Network-on-Chip (NoC) is a preferred communi- cation medium for massively parallel platforms. Fixed-priority based scheduling using virtual-channels is one of the promising solutions to support real-time traffic in on-chip networks. Most of the existing NoC implementations which can support fixed- priority based scheduling use a flit-level preemptive scheduling. Under such a mechanism, preemptions can happen between the transmissions of successive flits. In this paper, we present a modified framework where the non-preemptive region of each NoC packet increases from a single flit. Using the proposed approach, the response times of certain packet flows can be reduced, which can thus improve the schedulability of the whole network. As a result, the utilization of NoCs can be improved by admitting more real-time traffic. Schedulability tests regarding the proposed framework are presented along with the proof of the correctness. Moreover, a number of experiments as well as a case study based on an automotive application have been generated, where we can clearly observe the improvement of our solution compared to the original flit-level preemptive NoC.
|
|
| 229. |
- Liu, Meng, et al.
(författare)
-
Tighter Time Analysis for Real-Time Traffic in On-Chip Networks with Shared Priorities
- 2016
-
Ingår i: 2016 10th IEEE/ACM International Symposium on Networks-on-Chip, NOCS 2016.
-
Konferensbidrag (refereegranskat)abstract
- The Network-on-Chip (NoC) is the preferred inter- connection medium for massively parallel platforms. Targeting real-time applications, fixed-priority based NoCs with virtual- channels have been proposed as a promising solution. In order to verify if specific time requirements can be satisfied, scheduability tests are typically used. Several analysis approaches have been proposed targeting priority-based NoCs. However, due to the approximation considered in the analyses, the results may involve a large amount of pessimism. The applicability of the analyses is thus limited in practice. In this paper, we identify a number of properties of NoCs with shared priorities. An improved time analysis is proposed where pessimism can be significantly reduced for many cases. In order to evaluate the proposed analysis, a number of experiments have been generated along with a case study based on an automotive application. The improvement can be clearly observed from the evaluation results.
|
|
| 230. |
- Liu, Meng, et al.
(författare)
-
Towards Stochastic Response Time Analysis for CAN Messages with Multiple Probabilistic Factors
- 2015
-
Ingår i: The 21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, WiP RTCSA-wip'15. - Hong Kong, HongKong.
-
Konferensbidrag (refereegranskat)abstract
- Controller Area Network (CAN) is a widely used real-time network in the vehicular domain. In this paper we identify and discuss two practical parameters, namely message copy time and mixed transmission pattern, that can vary randomly during the execution of the system. We propose to leverage on these parameters to extend the existing stochastic Response Time Analysis (RTA) for CAN.
|
|
