With the growing complexity of modern embedded real-time systems, scheduling and managing of resources has become a daunting task. While scheduling and resource management for internal events can be simplified by adopting a commonplace real-time operating system (RTOS), scheduling and resource management for external events are left in the hands of the programmer, not to mention managing resources across the boundaries of external and internal events. In this paper we propose a unified system view incorporating earliest deadline first (EDF) for scheduling and stack resource policy (SRP) for resource management. From an embedded real-time system view, EDF+SRP is attractive not only because stack usage can be minimized, but also because the cost of a pre-emption becomes almost as cheap as a regular function call, and the number of preemptions is kept to a minimum. SRP+EDF also lifts the burden of manual resource management from the programmer and incorporates it into the scheduler. Furthermore, we show the efficiency of the SRP+EDF scheme, the intuitiveness of the programming model (in terms of reactive programming), and the simplicity of the implementation.
Dynamic memory management is typically implemented using a global memory allocator, which may negatively impact the performance, reliability, and predictability of a program; in effect standards around safety-critical applications often discourage or even disallow dynamic memory management. This paper presents heapless, a collection of dynamic data structures (for vectors, strings, and circular buffers) that can be either stack or statically allocated, thus free of global allocator dependencies. The proposed data structures for vectors and strings closely mimic the Rust standard library implementations while adding support to gracefully handling cases of capacity exceedance. Our circular buffers act as queues and allowing channel like usage (by splitting). The Rust memory model together with the ability of local reasoning on memory requirements (brought by heapless) facilitates establishing robustness/safety guarantees and minimize attack surfaces of (industrial) IoT systems. We show that the heapless data structures are highly efficient and have predictable performance, thus suitable for hard real-time applications. Moreover, in our implementation heapless data structures are non-relocatable allowing mapping to hardware, useful, e.g., to DMA transfers. The feasibility, performance, and advantages of heapless are demonstrated by implementing a JSON serialization and de-serialization library for an ARM Cortex-M based IoT platform.
The increased need for mobility has led to transportation problems like congestion, accidents and pollution. In order to provide safe and efficient transport systems great efforts are currently being put into developing Intelligent Transport Systems (ITS) and cooperative systems. In this paper we extend proposed solutions with autonomous on-road sensors and actuators forming a wireless Road Surface Network (RSN). We present the RSN architecture and design methodology and demonstrate its applicability to queue-end detection. For the use case we discuss the requirements and technological solutions to sensor technology, data processing and communication. In particular the MAC protocol is detailed and its performance assessed through theoretical verification. The RSN architecture is shown to offer a scalable solution, where increased node density offers more precise sensing as well as increased redundancy for safety critical applications. The use-case demonstrates that RSN solutions may be deployed as standalone systems potentially integrated into current and future ITS. RSN may provide both easily deployable and cost effective alternatives to traditional ITS (with a direct impact independent of penetration rate of other ITS infrastructures - i.e., smart vehicles, safe spots etc.) as well as provide fine grain sensory information directly from the road surface to back-end and cooperative systems, thus enabling a wide range of ITS applications beyond current state of the art.
Engineering and computer science have come up with a variety of techniques to increase the confidence in systems, increase reliability, facilitate certification, improve reuse and maintainability, improve interoperability and portability. Among them are various techniques based on formal models to enhance testing, validation and verification. In this paper, we are concentrating on formal verification both at runtime and design time of a system. Formal verification of a system property at design time is the process of mathematically proving that the property indeed holds. At runtime, one can check the validity of the property and report deviations by monitoring the system execution. Formal verification relies on semantic models, descriptions of the system and its properties. We report on ongoing verification work and present two different approaches for formal verification of IEC 61499-based programs. We provide two examples of ongoing work to exemplify the design and the runtime verification approaches
Samlingsprojekt för alla ESIS-projekt
Technology for the real time measurement of mechanical data from a javelin throw has been developed. The javelin is instrumented with an ineartial measurement unit measuring, IMU, acceleration, angle speed and direction to the earth magnetic field all in three dimensions i.e. in total nine parameters. The IMU is buildt into the javelin still maintaining the javelin properties and keeping it within the IAAF specifications. The instrumentation is build using the EIS architecture thus incorporating TCP/IP support including an Internet server. The wireless communication technology choosen is Bluetooth that connects to Internet through either a Bluetooth enabled mobile phone or a stationary Bluetooth accesspoint
We envision ambient intelligent environments with an infrastructure based on heterogeneous sensor and actuator devices accessible over the Internet. Initial steps to realize this concept have been taken by developing an Embedded Internet System (EIS) architecture for Internet protocol enabled devices. In many cases these devices will be in close proximity to a person. Such applications are found in for example sport and wellness. The mobile connection of such devices to the global Internet in a simple and cheap way is of particular interest. It is here proposed that such connection will make use of the existing and wide spread mobile phone networks. Since a few years most new mobile phones are equipped with Bluetooth technology making a mobile phone capable of connecting to 7 other Bluetooth devices. Thus by giving EIS devices a Bluetooth communication channel it will become possible to tunnel the EIS sensor communication through a mobile phone nearby the sensor. The proposed architecture will be described with discussion on limitations due to existing infrastructures and business models in the telecom networks.
This paper is a review of the fascinating development of sensors and the communication of sensor data. A brief historical introduction is given, followed by a discussion on architectures for sensor networks. Further, realistic specifications on sensor devices suitable for ambient intelligence and ubiquitous computing are given. Based on these specifications, the status and current frontline development are discussed. In total, it is shown that future technology for ambient intelligence based on sensor and actuator devices using standardized Internet communication is within the range of possibilities within five years.
In modern design flows low-power aspects should be considered as early as possible to minimize power dissipation in the resulting circuit. A new binary decision diagram-based design style that considers switching activity optimization using temporal correlation information is presented. The technique is based on an approximation method for switching activity estimation. In the case of finite state machines, the presented method extracts signal statistics by means of Markov chain analyses. Experimental results on a set of MCNC and ISCAS89 benchmarks show the estimated reduction in power dissipation.
Vid dödnätstart av produktionsanläggningar och drift av svaga nät eller ö-drift är frekvensomriktare som driver pumpar och fläktar kritiska komponenter. Om frekvensomriktare påverkas av störningar i nätet kan elproduktion kopplas bort och det svaga nätet eller ö-driften kollapsa. Projektet ska studera frekvensomriktare ur ett antal aspekter såsom uppbyggnad, styrning och implementering i syfte att utveckla mer robusta frekvensomriktare och implementering av dessa för att säkerställa drift av svaga nät och ö-drift och minimera ytterligare driftstörningar vid svåra påfrestningar på elnätet.
TCP/IP has recently taken promising steps toward being a viable communication architecture for networked sensor nodes. Furthermore, the use of Bluetooth can enable a wide range of new applications, and in this article, an overview of the performance and characteristics of a networked sensor node based on TCP/IP and Bluetooth is presented. The number of Bluetooth-enabled consumer devices on the market is increasing, which gives Bluetooth an advantage compared to other radio technologies from an interoperability point of view. However, this excellent ability to communicate introduces disadvantages since neither TCP/IP nor Bluetooth were designed with resource-constrained sensor nodes in mind. We, however, argue that the constraints imposed by general purpose protocols and technologies can be greatly reduced by exploiting characteristics of the communication scheme in use and efficient and extensive use of available low-power modes. Furthermore, we claim that a Bluetooth-enabled networked sensor node can achieve an operating lifetime in the range of years using a total volume of less than 10 cm3. The Mulle Embedded Internet System (EIS), along with its advanced power management architecture, is presented as a case-study to support the claims.
Wireless sensor nodes are a versatile, generalpurpose technology capable of measuring, monitoring and controlling their environment. Even though sensor nodes are becoming ever smaller and more power efficient, there is one area that is not yet fully addressed; Power Supply Units (PSUs). Standard solutions that are efficient enough for electronic devices with higher power consumption than sensor nodes, such as mobile phones or PDAs, may prove to be ill suited for the extreme low-power and size requirements often found on wireless sensor nodes. In this paper, a system-level design of a Power Management Architecture (PMA) is presented. The PMA is an integration of PSU hardware and various software components, and is capable of supplying a sensor node with energy from multiple sources, as well as providing status information from the PSU. The heart of the architecture is a context- and power-aware Task manager, which controls when the nodes low-power modes are activated, and is highly integrated with PSU hardware as well as other software components in the system. Its main responsibility is to schedule when energy consuming tasks can be dispatched. Depending on the task priority and system configuration, a task can be either dispatched, discarded or delayed. This approach ensures that only critical tasks will be allowed to use the battery, and that the system will be powered by renewable energy when performing other non-critical tasks.
Bluetooth-equipped wireless sensor nodes can be quickly integrated in small home networks. These networks can be utilized e.g. for surveillance, home monitoring and automation. Accurate time is an important factor for time-stamping of sensor data, encryption/authentication and it can also to used to implement time synchronous schemes for low power radio communication. We argue that IP-based time synchronization, such as various flavors of the NTP protocol, can be used with Bluetooth networks. This in combination with an activation schedule allows an efficient trade-off between energy consumption and communication delay, and provides easy integration with available infrastructure. The proposed approach in this paper is well suited for smaller wireless home networks, typically singlehop networks with access points that are always available. Our approach is verified by experiments performed on a COTS-based platform using Bluetooth.
Model and component based design is an established means for the development of large software systems, and is starting to get momentum in the realm of embedded software development. In case of safety critical (dependable systems) it is crucial that the underlying model and its realization captures the requirements on the timely behavior of the system, and that these requirements can be preserved and validated throughout the design process (from specification to actual code execution). To this end, we base the presented work on the notion of Concurrent Reactive Objects (CRO) and their abstraction into Reactive Components.In many cases, the execution platform puts firm resource limitations on available memory and speed of computations that must be taken into consideration for the validation of the system.In this paper, we focus on code synthesis from the model, and we show how specified timing requirements are preserved and translated into scheduling information. In particular, we present how ceiling levels for Stack Resources Policy (SRP) scheduling and analysis can be extracted from the model. Additionally, to support schedulability analysis, we detail algorithms that for a CRO model derives periods (minimum inter-arrival times) and offsets of tasks/jobs. Moreover, the design of a micro-kernel supporting cooperative hardware- and software-scheduling of CRO based systems under Deadline Monotonic SRP is presented.
Lightweight Real-Time Operating Systems have gained widespread use in implementing embedded software on lightweight nodes. However, bare metal solutions are chosen, e.g., when the reactive (interrupt-driven) paradigm better matches the programmer’s intent, when the OS features are not needed, or when the OS overhead is deemed too large. Moreover, other approaches are used when real-time guarantees are required. Establishing real-time and resource guarantees typically requires expert knowledge in the field, as no turn-key solutions are available to the masses.In this paper we set out to bridge the gap between bare metal solutions and traditional Real-Time OS paradigms. Our goal is to meet the intuition of the programmer and at the same time provide a resource-efficient (w.r.t. CPU and memory) implementation with established properties, such as bounded memory usage and guaranteed response times. We outline a roadmap for Real-Time For the Masses (RTFM) and report on the first step: an intuitive, platform-independent programming API backed by an efficient Stack Resource Policy-based scheduler and a tool for kernel configuration and basic resource and timing analysis.
In this paper, we present a comprehensive approach to design of embedded real-time software for electrically controlled mechanical systems in automotive applications. As a case study, we implement a Gear change and Clutch controller for a Formula SAE car. This includes a generic communication interface and protocol for CAN bus communication, I/O interfaces for A/D conversion and PWM output, together with a PID controller for clutch actuation. Under our framework, the embedded software is developed using Timber, a programming language and formalism that provides executable models for embedded real-time systems. The case study shows how a complete control system can be straightforwardly modeled, simulated and transformed into executable code. The system has been realized and tested onto a lightweight, 8-bit AVR-5, embedded platform. Compared to the raw C code design flow, the proposed framework has in our case study showed increased efficiency with respect to development time. We boldly conclude that our Timber based framework offers true "work with the work".
In this paper a distributed system for engine management is presented. The system is in use on the 2006 and 2005 Formula SAE cars from Luleå University of Technology. The purpose of building such a system from scratch is to have a comprehensive, predictable and easily extendable platform, giving the possibility to add extra features even at the racetrack. This allows the system to serve as a research platform for embedded real-time systems and vehicle dynamics. Another motivation is to get low weight on the complete system, and to integrate the electronics in such a way that the total cabling required will be minimal. The initial requirements are that the system should implement launch control, traction control, electric gear shift and clutch control. To control the engine the system must implement sequential fuel injection, direct fire ignition and closed loop lambda control. Moreover to remotely tune and monitor the system parameters in real-time - even on the racetrack, the system should facilitate wireless communication. To achieve these goals a system consisting of five units communicating over a standard automotive bus (CAN1) was developed. In this paper we will describe the systems functionality and the units developed.
A major challenge for the automotive industry is to reduce the development time while meeting quality assessments for their products. This calls for new design methodologies and tools that scale with the increasing amount and complexity of embedded systems in today's vehicles.In this paper we undertake an approach to embedded software design based on executable models expressed in the high-level modelling paradigm of Timber. In this paper we extend previous work on Timber with a multi-paradigm design environment, aiming to bridge the gap between engineering disciplines by multi-body co-simulation of vehicle dynamics, embedded electronics, and embedded executable models. Its feasibility is demonstrated on a case study of a typical automotive application (traction control), and its potential advantages are discussed, as highlighted below:shorter time to market through concurrent, co-operative distributed engineering, andreduced cost through adequate system design and dimensioning, andimproved efficiency of the design process through migration and reuse of executable software components, andreduced need for hardware testing, by specification verification on the executable model early in the design process, andimproved quality, by opening up for formal methods for verification.
This paper describes a system where Internet-enabled sensor technology was integrated into a context-aware platform to give viewers of sport events an enriched media experience. The system was developed as a proof of concept and was evaluated during real-life use at the Vasaloppet cross-country ski event. Using Bluetooth wireless ad-hoc networking and GPRS technology, sensor data was transmitted from contestants to the context-aware platform Alipes, which in turn presented the sport event viewer with a personalized, context-aware view. In this paper we discuss the system architecture and integration of components. The system was evaluated both from technical and user perspectives, where the evaluation results confirm our approach to be technically feasible and that the system provide an enriched media-experience for the majority of viewers.
We describe a method for generating logic simulation code which correctly responds to any number of undefined logic values at the code inputs. The method is based on our development of the ordered ternary decision diagram, itself based on Kleenean ternary logic, which explicitly and correctly manages the unknown logic value `U' in addition to the `1' and `0' of conventional OBDDs. We describe the OTDD and how to implement its reduction, application, and restriction operations. This method avoids expensive technology mapping, producing highly efficient `U'-correct compiled logic simulation code in seconds rather than in hours. Our experiments toward confirming the validity of the method are reported
Sammanfattningsvis är forskningsmålet att optimera kretskortsproduktion för små och medelstora serier. Huvudsakligen handlar det om att undersöka och modellera det termiska systemet mellan kretskort och lödugn. Modellen kommer sedan att användas för att ge bättre konfigurationsparametrar för produktionslinjen. En bra modell kommer inte bara att öka lödningskvalitén och minska antalet kasserade kretskort men kan också även användas för att hitta avvikelser redan i kretskortsdesignen.
The elderly population is growing rapidly. Fall related injuries are a central problem for this population. Elderly people desire to live at home, and thus, new technologies, such as automated fall detectors, are needed to support their independence and security. The aim of this study was to evaluate different low-complexity fall detection algorithms, using triaxial accelerometers attached at the waist, wrist, and head. The fall data were obtained from standardized types of intentional falls (forward, backward, and lateral) in three middle-aged subjects. Data from activities of daily living were used as reference. Three different detection algorithms with increasing complexity were investigated using two or more of the following phases of a fall event: beginning of the fall, falling velocity, fall impact, and posture after the fall. The results indicated that fall detection using a triaxial accelerometer worn at the waist or head is efficient, even with quite simple threshold-based algorithms, with a sensitivity of 97-98% and specificity of 100%. The most sensitive acceleration parameters in these algorithms appeared to be the resultant signal with no high-pass filtering, and the calculated vertical acceleration. In this study, the wrist did not appear to be an applicable site for fall detection. Since a head worn device includes limitations concerning usability and acceptance, a waist worn accelerometer, using an algorithm that recognizes the impact and the posture after the fall, might be optimal for fall detection.
About one third of home-dwelling people over 65 years of age fall each year. Falling, and the fear of falling, is one of the major health risks that affects the quality of life among older people, threatening their independent living. In our pilot study, we found that fall detection with a waist-worn triaxial accelerometer is reliable with quite simple detection algorithms. The aim of this study was to validate the data collection of a new fall detector prototype and to define the sensitivity and specificity of different fall detection algorithms with simulated falls from 20 middle-aged (40-65 years old) test subjects. Activities of daily living (ADL) performed by the middle-aged subjects, and also by 21 older people (aged 58-98 years) from a residential care unit, were used as a reference. The results showed that the hardware platform and algorithms used can discriminate various types of falls from ADL with a sensitivity of 97.5% and a specificity of 100%. This suggests that the present concept provides an effective method for automatic fall detection.
Software development for small, real-time and resource constrained, embedded systems is becoming increasingly complex. To be able to guarantee robustness and reliability, the underlying infrastructure should not be based upon ad hoc solutions. In this paper we identify three key features of a minimalistic Real-Time Operating System (RTOS), and presents the run-time system of Timber, a reactive deadlinedriven programming language. We scrutinize the functionalities of the run-time system in the light of real-time requirements, and emphasize the importance of integrating an adequate notion of time, both semantically in the programming interface as well as part of the run-time system.
Designing a garbage collector with real-time properties is a particularly difficult task, involving the construction of both an incremental run-time algorithm as well as methods enabling a priori reasoning about schedulability in two dimensions (time and memory usage in conjunction). In order to comply with such ambitious goals with any amount of formal rigor, a comprehensive understanding of the actual algorithm used is of course a fundamental requirement. In this paper we present a formal model of an incremental copying garbage collector, where each atomic increment is modeled as a transition between states of a heap process. Soundness of the algorithm is shown by proving that the garbage collecting heap process is weakly bisimilar to a non-collecting heap with infinite storage space. In addition, we show that our collector is both terminating and useful, in the sense that it actually recovers the unreachable parts of any given heap in a finite number of steps.
A technique for computing the switching activity of synchronous finite state machine (FSM) implementations including the influence of temporal correlation among the next state signals is described. The approach is based upon the computation that a FSM is in a given state which, in turn, is used to compute the conditional probability that a next state bit changes given its present state value. All computations are performed using decision diagram (DD) data structures. As an application of this method, the next state activity information is utilized for low power optimization in the synthesis of binary decision diagram (BDD) mapped circuits. Experimental results are presented based on a set of the ISCAS89 sequential benchmarks showing an average power reduction of 40 percent and tip to 90 percent reduction for individual benchmarks on the estimated power dissipation.
We present the idea of scheduling a control network in a first-come first-serve manner, and demonstrate a way to implement this over a wireless link. This achieves real-time guarantees and tightly bounded jitter for control applications. Further, how to design systems using this network is discussed, and the benefits compared to a standard priority MAC protocol are examined through simulations and a prototype implementation. The prototype is implemented using the reactive Timber programming model on a lightweight 8-bit platform.
Design methodology of digital circuits is a rapidly changing field. In the last 20 years, the number of transistors on a single chip has increased from thousands to tens of millions. This sets new demands on the design tools involved, their ability to capture specifications on a high level, and finally synthesize them into hardware implementations. The introduction of Decision Diagrams (DDs) has brought new means towards solving many of the problems raised by the increasing complexity of todays designs. In this thesis, we study their use in VLSI CAD and develop a number of novel applications. Incomplete specifications are inherent to the functionality of almost all digital circuits. We present a design methodology providing a common basis between design validation and logic synthesis, namely the semantics of Kleenean Strong Ternary Logic. This is called upon as commonly used design methodologies, based e.g. on VHDL are shown to put design correctness in jeopardy. By an extension of DDs, we can efficiently represent and manipulate incompletely specified functions. The method presented, not only guarantees correctness of the final circuit, but also offers potential towards expressing and utilizing incompleteness in ways other methodologies are incapable of. The increasing density and speed of todays target technologies also changes the conditions for logic synthesis; e.g., traditional quality measures based on gate delays are becoming less accurate as delays caused by interconnections are raising their heads. To address this problem we propose methodologies allowing quality measures of the final circuit to be foreseen and considered throughout the whole synthesis process. In general this is a very hard task. We approach the problem by limiting our synthesis methodologies to those rendering regular layouts (Such as computational arrays and lattices). The regularity allows us to predict properties of the final circuit and at the same time, ensure design criteria to be met, e.g., path delays and routability of the final circuit. In this thesis, we develop new design methodologies and their algorithms. By our experimental results, they are shown to offer significant improvements to both state of the art two-level and multi-level based tools in the area of layout driven synthesis. Our minimization methods are based on Pseudo Kronecker Decision Diagrams (PKDDs) which are the most general type of ordered bitlevel diagrams for switching functions. In the thesis we elaborate on the properties of PKDDs and Ternary PKDDs (TPKDDs) and develop an efficient minimization method based on local variable exchange for TPKDDs. Furthermore, the problem of PKDD minimization is discussed and a number of different strategies are introduced and evaluated; the potential compactness of PKDDs is confirmed. The thesis spans from validation and verification of high-level specifications all the way down to layout driven synthesis, combining logic minimization, mapping and routing to the target architecture at hand. We conclude our work to offer new means towards solving many of the crucial problems occurring along the design process of modern digital circuits.
We investigate the properties of the Ordered Ternary Decision Diagram (OTDD) in order to develop an efficient general OTDD package. The OTDD is a three-branched three-terminal diagram based on Kleenean strong ternary logic. The OTDD can represent functions having nontrivial don't-care sets in a single diagram and is capable of provably correct evaluation in the presence of unknown input values. We propose a number of improvements to both OTDD computational methods and data structures. Furthermore we introduce the purged form OTDD which unifies the abbreviated and full form OTDD into a single diagram. A package exploiting these OTDD specific properties is presented and we show the computational advantages of this improved package for LGSynth93 standard benchmarks.
The EIS architecture group at EISLAB performs research on design methodologies, tools and realizations of Embedded Internet Systems. Key to our research is the concept of reactivity; reactivity in the sense that a system reacts to events, either internal to the system or caused by its environment. This is manifested through the modeling paradigm of Timber with the ultimate goal of low-power, robust, scalable, distributed systems, with formally established real-time properties. The reactive approach is applied throughout the system design, all the way from protocols for service discovery, Internet Protocol based communication, down to analog and digital sensor interfaces. By collaboration with the Mixed mode design group, the theoretical work can be demonstrated in real-world applications.• EU FP6 SOCRADESIn the EU FP6 SOCRADES project, EISLAB investigatesarchitectures and protocols for real-time control over wireless links.• The AmI LabEfficient code generation from Timber models.• CASTTThrough the Center for Automotive Systems Technologies and Testing (CAST), Luleå University of Technology aims to first of all support automotive winter testing in Northern Sweden. • PhD PolisIn this bilateral Luleå-Oulo project, modular design of communication protocols is in focus. Ongoing work investigates how the Timber real-time semantics and strong type system can be utilized towards modular software design with formally established real-time behavior. • Intereg, Larmband – SensorbandTogether with Hälsovetenskap LTU, Caretech AB, Meri Lappi Institute, National Semiconductor Kemi, and Medical Technology at Oulu University, a ultra low-power prototype system for fall detaction is being developed.
We describe the algorithms for symbolic cycle simulation of sequential designs containing hierarchies of icompletely specified functions and Boolean relations. We propose the SSTG (symbolic state transition graph), which captures both the propagation of unknown input values and the effect of icomplerteness in the specification, and we develop algorithms for SSTG closure detection. Input vectors can be presented as Boolean relations, both spatial and temporal, on previous sets of input vectors, internal states and output vectors. Moreover the SSTG can be used towards verifying the correctness of the design with repect to both synthesis and redesign.
For the future we foresee each vehicle to feature wireless communication (to the Internet and/or other vehicles) over various technologies, e.g., UMTS/GPRS, and WLAN/WiFi. In this paper we show how access to such communication resources could be granted to individual components (CAN bus connected ECUs) in the car by allowing transparent data transport using the standardized Internet Protocol (IP). Our experiments show that a complete IP Over CAN implementation, providing both UDP and TCP transport over IP, running on an Atmel AT90CAN128 is capable of transfer speeds up to 200 kbits while using less than 2 kbytes of dynamic RAM.
The problem of general 2-level AND/EXOR minimization is known to be hard and proposed heuristic methods tend to be time consuming. Pseudo Kronecker Expressions (PSDKROs) are an interesting subclass as an upper bound estimate of moderate size can be efficiently derived in many cases.
Pseudo Kronecker expressions (PSDKROs) are a class of AND/EXOR expressions. For a Boolean function with a given variable order the minimal PSDKRO can be derived efficiently using decision diagram (DD) techniques. The quality, i.e., the number of products in the expression, of the result is known to be dependent on the variable ordering. This paper proposes several improvements and enhancements to previous minimization methods. A pruning technique that can be tuned to tradeoff quality for computational resources is presented. By applying dynamic ordering methods, significant improvements to many previously reported results are obtained. Furthermore, a new method for the minimization of multiple output functions is outlined. Experiments on a set of MCNC benchmarks confirm the advantages of the presented algorithms.
In this paper we outline a method for Look-up Table-FPGA (LUT-FPGA) synthesis from minimized Multi-Valued Pseudo Kronecker Expressions (MV PSDKROs). By restricting logic minimization to consider only easily mappable expressions, a regular Cellular Architecture (CA) layout without routing overhead is obtained. In this way our method combines logic minimization, mapping and routing. The transformation into the MV domain reduces the area as the number of products in the PSDKRO expression can be further minimized. Deriving the exact minimum MV PSDKRO is known to be hard or even intractable. We address this by applying pruning techniques based on cost estimation and dynamic methods to find suitable variable orderings. Results on a set of MCNC benchmarks show the advantages of the proposed minimization methods
The design process of digital circuits is often carried out in individual steps, like logic minimization, mapping and routing. This leads to quality loss e.g., in cases where highly optimized netlists fit badly onto the target architecture. Lattice diagrams have been proposed as one possible solution. They offer a regular two dimensional structure, thus overcoming the routing problem. However elegant, presented methods have only shown to find practical lattice representations for small functions. We present heuristic synthesis methods for Pseudo-Symmetric Pseudo Kronecker Decision Diagrams (PSPKDDs) applicable to incompletely specified multiple output functions. The lattice structure maps directly to both ASICs and fine grain FPGAs. Our method (combining logic minimization, mapping and routing) seeks to minimize area and delay by heuristic methods. Experimental results on a set of MCNC benchmarks show superior quality to previous methods and in many cases even optimal depth results for unfolded lattices.
The design process of digital circuits is often carried out in individual steps, like logic minimization, mapping and routing. This leads to quality loss, e.g. in cases where highly optimized netlists fit badly onto the target architecture. Lattice diagrams have been proposed as one possible solution. They offer a regular two dimensional structure, thus overcoming the routing problem. However elegant, presented methods have only been shown to find practical lattice representations for small functions. We present heuristic synthesis methods for Pseudo-Symmetric Pseudo Kronecker Decision Diagrams (PSP-KDDs) applicable to incompletely specified multiple output functions. The lattice structure maps directly to both ASICs and fine grain FPGAs. Our method (combining logic minimization, mapping and routing) seeks to minimize area and delay by heuristic methods. Experimental results on a set of MCNC benchmarks show superior quality to previous methods and in many cases even optimal depth results for unfolded lattices
The introduction of Decision Diagrams (DDs) has brought new means towards solving many of the problems involved in digital circuit design. Compactness of the representation is one key issue. Ordered Pseudo Kronecker Decision Diagrams (OPKDDs) together with the use of complemented edges is known to offer the most general ordered read-once DD representation at the bit-level, hence OPKDDs hold all minimal sized bit-level ordered DDs for a given function. This representation allows us to trade-off diagram canonicity against compactness. Ternary-OPKDDs (TOPKDDs) implicitly holds all OPKDDs for a given variable order. We state the canonicity criteria for TOPKDDs having complemented edges and develop an efficient sifting based method for their minimization. Furthermore, a heuristic minimization algorithm for OPKDDs is devised, utilizing the redundancies of Ternary-OPKDDs (TOPKDDs). Experiments on a set of MCNC benchmarks confirm the potential compactness of OPKDDs and demonstrate the efficiency of the proposed heuristics.
Embedded systems are often operating under hard real-time constraints. Such systems are naturally described as time-bound reactions to external events, a point of view made manifest in the high-level programming and systems modeling language Timber. In this paper we demonstrate how the Timber semantics for parallel reactive objects translates to embedded real-time programming in C. This is accomplished through the use of a minimalistic Timber Run-Time system, TinyTimber (TT). The TT kernel ensures state integrity, and performs scheduling of events based on given time-bounds in compliance with the Timber semantics. In this way, we avoid the volatile task of explicitly coding parallelism in terms of processes/threads/semaphores/monitors, and side-step the delicate task to encode time-bounds into priorities. In this paper, the TT kernel design is presented and performance metrics are presented for a number of representative embedded platforms, ranging from small 8-bit to more potent 32-bit micro controllers. The resulting system runs on bare metal, completely free of references to external code (even C-lib) which provides a solid basis for further analysis. In comparison to a traditional thread based real-time operating system for embedded applications (FreeRTOS), TT has tighter timing performance and considerably lower code complexity. In conclusion, TinyTimber is a viable alternative for implementing embedded real-time applications in C today.
The IEC 61499 standard provides means to specify distributed control systems in terms of function blocks. For the deployment, each device may hold one or many logical resources, each consisting of a function block network with service interface blocks at the edges. The execution model is event driven (asynchronous), where triggering events may be associated with data (and seen as a message). In this paper we propose a low complexity implementation technique allowing to asses end-to-end response time of event chains spanning a networked devices. Based on a translation of IEC 61499 to RTFM-tasks and resources, the response time for each task in the system can be derived using established scheduling techniques. In this paper we develop a method to provide safe end-to-end response time taking both intra- and inter-device delivery delays into account. As a use case we study the implementation onto (single-core) ARMcortex based devices communicating over a switched Ethernet network. For the analysis we define a generic switch model, and an experimental setup allowing us to study the impact of network topology as well as 802.1Q quality of service in a mixed critical setting. Our results indicate that safe sub milli-second end-to-end response times can be obtained using the proposed approach.