7975456
Schedulability-driven frame packing for multi-cluster distributed embedded systems
We present an approach to frame packing for multi-cluster distributed embedded systems consisting of time-triggered and event-triggered clusters, interconnected via gateways. In our approach, the application messages are packed into frames such that the application is schedulable. Thus, we have also proposed a schedulability analysis for applications consisting of mixed event-triggered and time-triggered processes and messages, and a worst case queuing delay analysis for the gateways, responsible for routing inter-cluster traffic. Optimization heuristics for frame packing aiming at producing a schedulable system have been proposed. Extensive experiments and a real-life example show the efficiency of our frame-packing approach.
1992062
Inter-domain movement of functionality as a repartitioning strategy for hardware/software co-design
Abstract This paper describes how initial hardware/software partitions can be modified by moving functionality between hardware and software. This inter-domain movement of functionality combined with a transformation-based design methodology enables the use of repartitioning as an optimization technique for co-design. This is made possible because of a unified co-design representation where Petri nets are used to represent controllers of both hardware and software module. To model data manipulation we use datapaths in hardware and instruction dependence graphs in software. We demonstrate in this paper how datapaths can be mapped into instruction dependence graphs and vice versa. Using this technique, systems may be repartitioned whithout the complex and time-consuming resynthesis of the functionality to be moved or the whole design.
62487698
The Design and Optimization of SOC Test Solutions
We propose an integrated technique for extensive optimization of the final test solution for System-on-Chip using Simulated Annealing. The produced results from the technique are a minimized test schedule fulfilling test conflicts under test power constraints and an optimized design of the test access mechanism. We have implemented the proposed algorithm and performed experiments with several benchmarks and industrial designs to show the usefulness and efficiency of our technique.
10777322
Overhead-conscious voltage selection for dynamic and leakage energy reduction of time-constrained systems
Dynamic voltage scaling and adaptive body biasing have been shown to reduce dynamic and leakage power consumption effectively. In this paper, we optimally solve the combined supply voltage and body bias selection problem for multi-processor systems with imposed time constraints, explicitly taking into account the transition overheads implied by changing voltage levels. Both energy and time overheads are considered. We investigate the continuous voltage scaling as well as its discrete counterpart, and we prove NP-hardness in the discrete case. Furthermore, the continuous voltage scaling problem is formulated and solved using nonlinear programming with polynomial time complexity, while for the discrete problem we use mixed integer linear programming. Extensive experiments, conducted on several benchmarks and a real-life example, are used to validate the approaches.
10406156
Schedulability Analysis and Optimization for the Synthesis of Multi-Cluster Distributed Embedded Systems
We present an approach to schedulability analysis for the synthesis of multi-cluster distributed embedded systems consisting of time-triggered and event-triggered clusters, interconnected via gateways. We have also proposed a buffer size and worst case queuing delay analysis for the gateways, responsible for routing inter-cluster traffic. Optimization heuristics for the priority assignment and synthesis of bus access parameters aimed at producing a schedulable system with minimal buffer needs have been proposed. Extensive experiments and a real-life example show the efficiency of our approaches.
9707498
Efficient test solutions for core-based designs
A test solution for a complex system requires the design of a test access mechanism (TAM), which is used for the test data transportation, and a test schedule of the test data transportation on the designed TAM. An extensive TAM will lead to lower test-application time at the expense of higher routing costs, compared to a simple TAM with low routing cost but long testing time. It is also possible to reduce the testing time of a testable unit by loading the test vectors in parallel, thus increasing the parallelization of a test. However, such a test-time reduction often leads to higher power consumption, which must be kept under control since exceeding the power budget could damage the system under test. Furthermore, the execution of a test requires resources and concurrent execution of tests may not be possible due to resource or other conflicts. In this paper, we propose an integrated technique for test scheduling, test parallelization, and TAM design, where the test application time and the TAM routing are minimized, while considering test conflicts and power constraints. The main features of our technique are the efficiency in terms of computation time and the flexibility to model the system's test behavior, as well as the support for the testing of interconnections, unwrapped cores and user-defined logic. We have implemented our approach and made several experiments on benchmarks as well as industrial designs in order to demonstrate that our approach produces high-quality solution at low computational cost.
7761822
An integrated system-on-chip test framework
In this paper we propose a framework for the testing of system-on-chip (SOC), which includes a set of design algorithms to deal with test scheduling, test access mechanism design, test sets selection, test parallelization, and test resource placement. The approach minimizes the test application time and the cost of the test access mechanism while considering constraints on tests, power consumption and test resources. The main feature of our approach is that it provides an integrated design environment to treat several different tasks at the same time, which were traditionally dealt with as separate problems. Experimental results shows the efficiency and the usefulness of the proposed technique.
1176441
Secure Audit Logging with Tamper-Resistant Hardware
Secure perimeter schemes (e.g. DRM) and tracing traitor schemes (e.g. watermarking, audit logging) strive to mitigate the problems of content escaping the control of the rights holder. Secure audit logging records the user's actions on content and enables detection of some forms of tampering with the logs. We implement Schneier and Kelsey's secure audit logging protocol, strengthening the protocol by using tamper-resistant hardware (an iButton) in two ways: Firstly our implementation of the protocol works offline as well as online. Secondly, we use unforgeable time stamps to increase the possibilities of fraud detection. We provide a performance assessment of our implementation to show under which circumstances the protocol is practical to use.
7206861
Defect-aware SOC test scheduling
In this paper we address the test scheduling problem for system-on-chip designs. Different from previous approaches where it is assumed that all tests are performed until completion, we consider the cases where the test process are terminated as soon as a defect is detected. This is common practice in production test of chips. The proposed technique takes into account the probability of defect-detection by a test in order to schedule the tests so that the expected total test time is minimized. We investigate different test bus structures, test scheduling strategies (sequential scheduling vs. concurrent scheduling), and test set assumptions (fixed test time vs. flexible test time). We have also made experiments to illustrate the efficiency of taking defect probability into account during test scheduling.
46430059
An O(n log n)-Time Algorithm for the Maximum Constrained Agreement Subtree Problem for Binary Trees
This paper introduces the maximum constrained agreement subtree problem, which is a generalization of the classical maximum agreement subtree problem This new problem is motivated by the understood constraint when we compare the evolutionary trees We give an O(n log n)-time algorithm for solving the problem when the input trees are binary The time complexity of our algorithm matches the fastest known algorithm for the maximum agreement subtree problem for binary trees.
43458709
Algorithms for Local Forest Similarity
An ordered labeled tree is a rooted tree, where the left-to-right order among siblings is significant and each node associates a label. A forest is a sequence of ordered labeled trees. Suppose F is a forest. A substructure is a connected subgraph of F. Define a subforest as a sequence of substructures of F such that their roots are siblings. The local forest similarity problem for forests F and G is to find two most similar subforests of F and G. We answer an open problem in Paper [3], and provide efficient algorithms on it. Comparing with previous results, our algorithms achieve better performance.