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.
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.
9900155
An approach to incremental design of distributed embedded systems
In this paper we present an approach to incremental design of distributed embedded systems for hard real-time applications. We start from an already existing system running a set of applications and the design problem is to implement new functionality so that the already running applications are not disturbed and there is a good chance that, later, new functionality can easily be added to the resulted system. The mapping and scheduling problem are considered in the context of a realistic communication model based on a TDMA protocol.
27568459
Automated transformation of algorithms into register-transfer level implementations
This paper describes a high-level synthesis system, called CAMAD, for transforming algorithms into hardware implementation structures at register-transfer level. The algorithms are used to specify the behaviors of the hardware to be designed. They are first translated into a formal representation model which is based on timed Petri nets and consists of separate but related descriptions of control and data path. The formal model is used as an intermediate design representation and supports an iterative transformation approach to high-level synthesis. The basic idea is that once the behavioral specification is translated into the initial design representation, it can be viewed as a primitive implementation. Correctness-preserving transformations are then used to successively transform the initial design into an efficient implementation. Selection of transformations is guided by an optimization strategy which makes design decisions concerning operation scheduling, data path allocation, and control allocation simultaneously. The integration of these several synthesis subtasks has resulted in a better chance to reach the globally optimal solution. Experimental results show that our approach produces improved register-transfer designs, especially in the cases when the designed hardware consists of data paths and control logics that are tightly coupled. >
43554221
Online and Dynamic Recognition of Squarefree Strings
The online squarefree recognition problem is to detect the first occurrence of a square in a string whose characters are provided as input one at a time. We present an efficient algorithm to solve this problem for strings over arbitrarily ordered alphabets. Its running time is O(n log n), where n is the ending position of the first square, which matches the running times of the fastest known algorithms for the analogous offline problem. We also present a very simple algorithm for a dynamic version of the problem over general alphabets in which we are initially given a squarefree string, followed by a series of updates, and the objective is to determine after each update if the resulting string contains a square and if so, report it and stop.
8351252
Using object deputy model to prepare data for data warehousing
Providing integrated access to multiple, distributed, heterogeneous databases and other information sources has become one of the leading issues in database research and the industry. One of the most effective approaches is to extract and integrate information of interest from each source in advance and store them in a centralized repository (known as a data warehouse). When a query is posed, it is evaluated directly at the warehouse without accessing the original information sources. One of the techniques that this approach uses to improve the efficiency of query processing is materialized view(s). Essentially, materialized views are used for data warehouses, and various methods for relational databases have been developed. In this paper, we first discuss an object deputy approach to realize materialized object views for data warehouses which can also incorporate object-oriented databases. A framework has been developed using Smalltalk to prepare data for data warehousing, in which an object deputy model and database connecting tools have been implemented. The object deputy model can provide an easy-to-use way to resolve inconsistency and conflicts while preparing data for data warehousing, as evidenced by our empirical study.
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.
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.