As higher and higher functionalities are being im-plemented in embedded systems, it is becoming difficult to ensure their real-time performance. As one approach to enhancing response performance of RTOS-based systems, Oosako proposed a method for implementing both kernel objects and RTOS functionalities as hardware utilizing high-level synthesis, where TOP-PERS/ASP3 was assumed as an RTOS. This paper extends this method to deal with systems based on FreeRTOS. In FreeRTOS, tasks can be generated either statically or dynamically, whose control data are managed in linked lists. We place restrictions that all the tasks are generated before scheduler starts so that we can keep the task control data in an array. Software timers are dealt with as tasks that have their own timers. We also present methods to implement dispatch disabling for mutual exclusion and a data queue for asynchronous data communication. We have implemented a hardware module from a reduced version of a demo program main_full.c and TimerDemo.c bundled with FreeRTOS, which took less than 300 ns and 700 ns for task control and data queue operations, respectively.

This paper presents a method of automatically synthesizing a hardware design from a set of source codes for a real-time system utilizing an RTOS. It generates a full hardware implementation where all the tasks and handlers in the system as well as all the necessary services provided by the RTOS kernel are implemented as hardware. Every task and handler is synthesized into an independent hardware module so that it may run in parallel with the other tasks/handlers as soon as it is ready. This leads to task switching with extremely low overhead and reduced computation time both by parallel and hardware execution. Moreover, this eliminates the necessity of the task queue management; task scheduling is realized by a relatively simple manager hardware which instructs each task/handler to run or stall based on the values of its status variables. Since most of the API calls from tasks/handlers are reduced to reads/writes of these status variables, they can be expanded inline into the tasks/handlers source codes which are compiled into hardware designs by a high-level synthesizer. We have implemented a prototype synthesis system which assume the use of the TOPPERS/ASP3 real-time kernel. A hardware implementation synthesized from a sample 1.c code, bundled in the TOPPERS/ASP3 release, took 23 cycles for waking up a waiting task and only 1 cycle for activating an interrupt handler.

This article presents a method of synthesizing hardware from a given executable binary code with an external interrupt handler, where the normal flow and the interrupt handling are executed by separate hardware modules. Our previous method synthesized the whole program into a single hardware module, in which register save/restore imposed limitations on the timing to start interrupt handling and also impaired efficiency of the synthesized hardware. By executing the two tasks on separate modules, register save/restore can be eliminated, which allows interrupt handler to start at arbitrary timing and reduces the response time and cost of the hardware. By allowing two processes to run in parallel, total execution time is also reduced. An experiment with a simple program has shown that the execution cycles and the delay were reduced by about 80% and 20%, respectively, as compared with MIPS CPU. A motor controller driven by periodical interrupts from a timer has been successfully synthesized from C and assembly programs, which runs more than 20 times faster than the MIPS CPU.

This paper proposes a method of incorporating speculative execution into distributed control which enables efficient dynamic scheduling. In the presence of variable latency units, the static scheduling scheme in conventional high-level synthesis causes wasteful waits. Distributed control enables dynamic scheduling which adjust the execution timing of the operations dynamically. In this paper, we attempt to further enhance speed performance by introducing speculative execution based on branch prediction into distributed control. Experimental results on two examples showed that the execution cycles were reduced by 11.1% to 21.9% when the prediction hit rate was 75%.

This paper presents a method for thread partitioning for a hardware compiler Bach.Bach synthesizes RT level circuits from a system description written in Bach-C language, where a system is modeled as communicating processes running in parallel.The system description is decomposed into threads, i.e., strings of sequential processes, and then converted into synthesizable behavioral VHDL models.The proposed method attempts to find a partitioning of a given system description into threads that maximize resource sharing among processes in the threads.Experiments on two real designs show that the circuit sizes were reduced by 3.7% and 14.7%.We also show the detailed statistics and analysis of the size of the resulting gate level circuits.

This paper presents new binding and scheduling algorithms for a retargetable compiler which can deal with diverse architectures. Application specific embedded processors often includes a "nonorthogonal" datapath where all the registers are not equally accessible from all the functional units. Nonorthogonal datapath makes a binding task very hard because inadvertent assignment of an operation to a functional unit may rule out all the possible assignments to other operations due to reachability constraints among datapath resources. Scheduling must take register capacity constraints into account in addition to resource constraints. We discuss these problems and propose algorithms to solve them.

We propose a fault simulation technique for multiple faults based on a deductive fault simulation method. The main difficulty in the development of a technique for multiple fault simulation is handling a very large number of multiple faults. Conventional deductive simulation using Linear lists to store fault sets is not appropriate for such large sets of multiple faults. Our approach to this problem is to represent sets of multiple faults by Boolean functions. We assign a distinct code word to each multiple fault and represent the fault by a minterm corresponding to its code word. Then, set operations in deductive simulation are replaced by logic operations. As an internal representation of fault sets, we use shared binary decision diagrams. The method of coding multiple faults is a key to efficient simulation. We propose a coding method called FNT coding. We also propose a fault dropping method, called prime fault dropping, which is used efficiently with our multiple fault simulation technique. Experimental results show that our technique effectively handles multiple faults at significantly lower computation cost.>

Article Probabilistic CTSS: analysis of timing error probability in asynchronous logic circuits Share on Authors: Yutaka Deguchi Department of Information Science, Faculty of Engineering, Kyoto University, Kyoto 606, Japan Department of Information Science, Faculty of Engineering, Kyoto University, Kyoto 606, JapanView Profile , Nagisa Ishiura Department of Information Science, Faculty of Engineering, Kyoto University, Kyoto 606, Japan Department of Information Science, Faculty of Engineering, Kyoto University, Kyoto 606, JapanView Profile , Shuzo Yajima Department of Information Science, Faculty of Engineering, Kyoto University, Kyoto 606, Japan Department of Information Science, Faculty of Engineering, Kyoto University, Kyoto 606, JapanView Profile Authors Info & Claims DAC '91: Proceedings of the 28th ACM/IEEE Design Automation ConferenceJune 1991 Pages 650–655https://doi.org/10.1145/127601.127745Published:01 June 1991 7citation160DownloadsMetricsTotal Citations7Total Downloads160Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Boolean function manipulators based on Shared Binary Decision Diagrams (SBDD'S) =e utilized efficiently in various applications such as design verification.We propose a high-speed algorithm of manipulating SBDD'S, which can be used with a vector supercomputer effectively.This proposed algorithm is implement ed and evaluated on the vector supercomput er HI-TAC S-820/80.The vector acceleration ratio obtained is 14.3 in the best case. 1

The authors present a novel exact algorithm and gradual improvement methods for minimizing binary decision diagrams (BDDs). In the exact minimization algorithm, the optimum order is searched by the exchanges of variables of BDDs based on the framework of the algorithm of S.J. Friedman and K.J. Supowit (1990). The use of the BDD representation of a given function and intermediate functions makes it possible to produce pruning into the method, which drastically reduces the computation cost. The authors succeeded in minimizing a 17-variable function by the use of the BDD representation of intermediate functions and the introduction of pruning. They also propose a greedy method and a simulated annealing method based on exchanges of two arbitrary variables, and a greedy method based on exchanges of adjacent m variables for m=3 and 4.>

The authors propose a novel fault simulation technique for multiple faults. In order to handle a large number of multiple faults, sets of multiple faults are represented by Boolean functions, in which shared binary decision diagrams (BDDs) are used as an internal representation of Boolean functions. The authors also propose a fault dropping method, prime fault dropping, which is used efficiently to execute multiple fault simulation. The authors have succeeded in simulating 39 million double faults of a circuit of 2300 gates with about 20 Mbyte storage.>

In this paper we propose a new timing verification technique named coded time-symbolic simulation, CTSS. We are concerned with simulation of logic circuits consisting of gates whose delay is specified only by its minimum and maximum values. We encode the cases of possible delay values of each gate by binary values and simulate all the possible combinations of the delay values by means of symbolic simulation. This simulation technique can deal with logic circuits containing feedback loops as well as combinational circuits. We implemented an efficient simulator by using a shared binary decision diagram (SBDD) as an internal representation of Boolean functions. We also propose novel techniques of analyzing the results of CTSS.

This paper describes a new behavioral model of hardware, named NES (Nondeterministic Event Sequence) model, which was developed for the purpose of defining formal semantics of the gate level and the register transfer level hardware description languages. The NES model is a generalization of the event driven simulation, and can be a basis of synthesis and verification as well as simulation. We introduce basic concepts, formal definition, and a description method of the NES model.

The efficiency of Boolean function manipulation depends on the form of representation of Boolean functions. Binary Decision Diagrams (BDD's) are graph representations proposed by Akers and Bryant. BDD's have some properties which can be used to enable efficient Boolean function manipulation.

UDL/I is a hardware design language for ASIC design developed in a Japanese LSI design language standardization project. A formal semantics of UDL/I is presented. There is no established way to define semantics of hardware design languages, because there is no general computation model for them. A definition method of formal semantics for UDL/I and semantics suitable for a standard language are developed. The basic idea is that the semantics of the language should be defined independently of simulators. The language provides an abstract model of hardware. The role of the language designer is to provide an abstract model of hardware which is natural and general for hardware designers and CAD engineers. The authors introduce a novel behavior model of hardware and define the semantics with a nondeterministic feature.>

An approach to accelerating fault simulation using a vector super computer is described and the zero-delay, two-valued fault simulation of gate-level combinational circuits is discussed. As a vector processor oriented simulation technique, an algorithm was developed that is based on the parallel fault simulation technique. In the technique, fault simulation can be accelerated (given that enough vector lengths can be obtained) to a maximum of 20 times faster using vector operations of a currently available vector computer by extending the processing unit from one word to multiple words. However, when fault simulation to generate or to evaluate test patterns is performed, enough vector length is not obtained or the computation time increases if large vector length is attempted because detected faults are dropped. In order to address the problems, a dynamic, two-dimensional, parallel fault simulation technique is proposed. In this technique, large vector length is obtained by utilizing both fault and pattern parallelism, and fault dropping is efficiently used to adjusting the two parallelism factors complementarily from pass to pass. The computation time is further reduced by combining this technique with selective tracing under the notion of multiple fault propagation. The experiments on the FACOM vector processor show that the simulation speed is accelerated by 10 to about 15 times through vectorization.>

As a new approach for timing verification of logic circuits, we propose a new concept of time-symbolic simulation. While a conventional symbolic simulator treats signal values as logical expressions, a time-symbolic simulator treats time as algebraic expressions. In this paper, we describe algorithms for time-symbolic simulation, and its application to hazard detection and verification of asynchronous sequential circuits.

We propose a new approach to define a formal semantics of a hardware design language (HDL) in Japanese LSI design language standardization project. Our approach is to separate the definition of semantics from simulators. Since the semantics includes nondeterminism, we can describe vagueness of circuit behavior such as dispersion of delays without linguistic ambiguity. We introduce a new computation model of hardware behaviour called NES (Nondeterministic Event Sequence) model. NES model is a very simple model of the computation in digital systems and provides an intuitive understanding of concurrent behaviour of HDL description without loss of mathematical strictness.

In this paper, we propose logic simulation techniques using vector processors, or supercomputers with pipeline architecture, as a new approach to accelerating simulation speed. In order to use vector processors efficiently, we have to tune up the coding scheme or the basic algorithms to be suitable for vector processing. We developed three types of new simulation techniques for vector processing, which are dedicated for (1) zero-delay simulation of combinational circuits, (2) zero-delay simulation of synchronous sequential circuits, and (3) simulation with delay consideration. The first two are based on the compiler-driven method and the last on the event-driven method. We implemented logic simulators based on the above techniques on the FACOM VP-100 and VP-200 at Kyoto University and on the HITAC S-810/20 at the University of Tokyo. The maximum performance is about 7.7 x 10 /sup 9/ gate-evaluations per second for combinational circuit simulation, 1.4 x 10 /sup 9/ gate-evaluations per second for sequential circuit simulation (on the VP-200), and 230 x 10 /sup 3/ events per second for timing simulation (on the S-810/20). These results are comparable to the performance of hardware simulation engines. Moreover, our techniques are so straightforward that we can implement them on most of the recent vector processors without serious modifications