Search

Traditionally, real-time scheduling algorithms prioritize tasks solely based on their timing parameters and cannot effectively handle tasks that have different execution preferences . In this paper, for a set of periodic real-time tasks running on a single processor, where some tasks are preferably executed as soon as possible (ASAP) and others as late as possible (ALAP) , we investigate Preference-Oriented Fixed-Priority (POFP) scheduling techniques. First, based on Audsley’s Optimal Priority Assignment (OPA) , we study a Preference Priority Assignment (PPA) scheme that attempts to assign ALAP (ASAP) tasks lower (higher) priorities, whenever possible. Then, by considering the non-work-conserving strategy, we exploit the promotion times of ALAP tasks and devise an online dual-queue based POFP scheduling algorithm. Basically, with the objective of fulfilling the execution preferences of all tasks, the POFP scheduler retains ALAP tasks in the delay queue until their promotion times while putting ASAP tasks into the ready queue right after their arrivals. In addition, to further expedite (delay) the executions of ASAP (ALAP) tasks using system slack, runtime techniques based on dummy and wrapper tasks are investigated. The proposed schemes are evaluated through extensive simulations. The results show that, compared to the classical fixed-priority Rate Monotonic Scheduling (RMS) algorithm, the proposed priority assignment scheme and POFP scheduler can achieve significant improvement in terms of fulfilling the execution preferences of both ASAP and ALAP tasks, which can be further enhanced at runtime with the wrapper-task based slack management technique. [ABSTRACT FROM AUTHOR]

Abstract: Future many-core processor systems require scalable solutions that conventional architectures currently do not provide. This paper presents a novel architecture that demonstrates the required scalability. It is based on a model of computation developed in the AETHER project to provide a safe and composable approach to concurrent programming. The model supports a dynamic approach to concurrency that enables self-adaptivity in any environment so the model is quite general. It is implemented here in the instruction set of a dynamically scheduled RISC processor and many such processors form a microgrid. Binary compatibility over arbitrary clusters of such processors and an inherent scalability in both area and performance with concurrency exploited make this a very promising development for the era of many-core chips. This paper introduces the model, the processor and chip architecture and its emulation on a range of computational kernels. It also estimates the area of the structures required to support this model in silicon. [Copyright &y& Elsevier]

With the recent proliferation of different types of Cyber Physical Systems (CPS), it is critically important to investigate the predictability of such systems. Along with functional correctness of the components, these systems must also ensure that timing and delay constraints of components are properly for the entire system to behave in a predictable manner in presence of various kinds of uncertainties. While the functional correctness of the CPS components has been investigated in the past, very little is available about the timing issues. The objective of this paper is to conduct an investigation of key issues involved to ensure the predictability of the system, introduce rigorous definitions of performance parameters, and propose metrics for their evaluation and analyze their suitability to be used in the presence of uncertainties in which CPS operate. The results are expected to provide greater insight into the time critical behavior of CPS components. [ABSTRACT FROM AUTHOR]

In this paper an efficient algorithm is proposed which optimizes periodic message scheduling in a real-time multiprocessor system. The system is based on a many-core single-chip computer architecture and uses a multistage baseline network for inter-core communication. Due to its basic architecture, internal blockings can occur during data transfers, i.e. the baseline network is not real-time capable by itself. Therefore, we propose a scheduling algorithm that may be performed before the execution of an application in order to compute a non-blocking schedule of periodic message transfers. Additionally, we optimize the clock rate of the network subject to the constraint that all data transfers can be performed in a non-blocking way. Our solution algorithm is based on a generalized graph coloring model and a randomized greedy approach. The algorithm was tested on some realistic communication scenarios as they appear in modern electronic car units. Computational results show the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study the adequacy of available schedulability tests for monoprocessor fixed-priority systems to enable performing scheduling analysis for automotive applications. We show that, in spite of the work carried out during the last decade to enhance these tests in order to support more realistic task model, a gap still exists between the task model considered in these tests and the usual automotive task model. However, we claim that an extension of these tests is possible to support some of the uncovered automotive features. The aim of this study is to raise discussion and make researchers involved in the development of such schedulability tests be aware of the effort needed to bridge the gap between current schedulability tests and automotive task model mostly used. The study is illustrated by showing the concrete challenges faced when applying scheduling analysis to a case study derived from a real engine control application. [Copyright &y& Elsevier]

Abstract: This paper presents a strategy for the design of real-time applications relying on the resource-reservation paradigm, based on a new modelling element that describes the schedulable entities of the applications during the whole design cycle. A virtual view of this element is used first for evaluating a set of constraints that guarantee the application schedulability independently of the execution platform. Then, the element is viewed as a thread that receives the particular scheduling parameters required for a schedulable execution of the application in a specific platform. The purpose of the design process is to make both views compatible. [Copyright &y& Elsevier]

Abstract: To provide a common ground for the comparison of real-time multicore synchronization protocols we developed a framework that supports heterogenous levels of abstraction for simulated functionality and simulated timing. Our intention is to make the simulator available to the real-time research community and industrial users. For the latter we initially focus on automotive real-time systems. This paper describes the simulation framework and the novel idea of heterogenous abstraction levels that lies at the heart of its design. Notwithstanding the clear focus, we believe that the simulator itself as well as the concept of heterogenous abstraction levels can be useful in a significantly broader way. [Copyright &y& Elsevier]

Abstract: We present an analysis of the virtualizability of the ARMv7-A architecture carried out in the context of the seminal paper published by Popek and Goldberg 38years ago. Because their definitions are dated, we first extend their machine model to modern architectures with paged virtual memory, IO and interrupts. We then use our new model to show that ARMv7-A is not classically virtualizable. Insights such as binary translation enable efficient virtualization beyond the original criteria. Companies are also making their architectures virtualizable through extensions. We analyse both approaches for ARM and conclude that both have their use in future systems. [Copyright &y& Elsevier]

Abstract: This paper proposes a new group-based acceleration data structure called gkDtree for interactive ray tracing of dynamic scenes. The main idea of the gkDtree is to construct the acceleration structure with a multi-level hierarchy, and to integrate a parallelization approach to result in a faster update and a more efficient tree traversal. A gkDtree can be viewed as a set of kd-trees, each of which is a local acceleration structure corresponding to a group. For a gkDtree, a scene is divided into several groups based on a scene graph. The local acceleration structure of each group involving only dynamic primitives is rebuilt. To achieve higher parallelization, dependencies among groups in different levels are removed before rebuilding occurs in parallel. To enhance the scalability of parallelization, a simple and fast load-balancing scheme is introduced. Furthermore, we apply a variety of accurate SAH (surface area heuristic) algorithms into tree generation for both static and dynamic groups. The experimental results show that a gkDtree has a real-time update performance. It has an update performance that is up to 166 times faster than a kd-tree for our test scenes in a six-core hardware system environment. Furthermore, the results also show that tree traversal performance of a gkDtree is competitive with that of a kd-tree. [Copyright &y& Elsevier]

Abstract: Validation and verification of embedded systems through simulation can be conducted at many levels, from the simulation of a high-level application model to the simulation of the actual binary code using an accurate model of the processor. However, for real-time applications, the simulated execution time must be as close as possible to the execution time on the actual platform and in this case the latter gives the closest results. The main drawback of the simulation of application’s software using an accurate model of the processor resides in the development of a handwritten simulator which is a difficult and tedious task. This paper presents Harmless, a hardware architecture description language (ADL) that mainly targets real-time embedded systems. Harmless is dedicated to the generation of simulators for hardware platforms to develop and test real-time embedded applications. Compared to existing ADLs, Harmless (1) offers a more flexible description of the instruction set architecture (ISA) (2) allows to describe the microarchitecture independently of the ISA to ease its reuse and (3) compares favorably to simulators generated by the existing ADLs toolsets. [Copyright &y& Elsevier]

Abstract: Dynamic binary translation (DBT) is an important technique in virtualization, and in migrating legacy binaries to platforms based on a new architecture. However, poor profile information limits the process of optimization at runtime, so the DBT system may suffer from substantial overhead. In this paper, we design and implement a static-integrated optimization framework (SINOF) to improve the runtime performance for DBT. Combining static and dynamic approaches can greatly reduce the overhead of optimizing, profiling and translating for any program that runs repeatedly. Under this framework, once the source image has been executed, the profile information and target code will be saved in a software cache, and will be available for future runs. In the static phase, the saved code is analyzed and optimized based on the information collected in the previous run. Especially, we reorganize the code layout of the software cache. Experimental results show that the proposed framework can reduce run time by more than 30% on average compared to the original versions of DBT that the framework is based on. [Copyright &y& Elsevier]

Abstract: Although component middleware is increasingly used to develop distributed, real-time and embedded (DRE) systems, it poses new fault-tolerance challenges, such as the need for efficient synchronization of internal component state, failure correlation across groups of components, and configuration of fault-tolerance properties at the component granularity level. This paper makes three contributions to R&D on component-based fault-tolerance. First, it describes the COmponent Replication based on Failover Units (CORFU) component middleware, which provides fail-stop behavior and fault correlation across groups of components treated as an atomic unit in DRE systems. Second, it describes how CORFU’s Components with HEterogeneous State Synchronization (CHESS) module provides mechanisms for real-time aware state transfer and synchronization in CORFU. Third, we empirically evaluate the client failover and group shutdown capabilities of CORFU and its CHESS module and compare/contrast it with existing object-oriented fault-tolerance methods. Our results show that component middleware (1) has acceptable fault-tolerance performance for DRE systems, (2) allows timely recovery while considering failure location, size, and functional topology of the group, and finally (3) eases the burden of application development by providing middleware support for fault-tolerance at the component level. [Copyright &y& Elsevier]

Abstract: Flash memory is a non-volatile memory which can be electrically erased and reprogrammed. Its major advantages such as small physical size, no mechanical components, low power consumption, and high performance have made it likely to replace the magnetic disk drives in more and more systems. However, flash memory has four specific features which are different to the magnetic disk drives, and pose challenges to develop practical techniques: (1) Flash memory is erased in blocks, but written in pages. (2) A block has to be erased before writing data to the block. (3) A block of flash memory can only be written for a specified number of times. (4) Writing pages within a block should be done sequentially. This survey presents the architectures, technologies, and optimization methods employed by the existing flash memory based storage systems to tackle the challenges. I hope that this paper will encourage researchers to analyze, optimize, and develop practical techniques to improve the performance and reduce the energy consumption of flash memory based storage systems, by leveraging the existing methods and solutions. [Copyright &y& Elsevier]

Abstract: Effective address calculations for load and store instructions need to compete for ALU with other instructions and hence extra latencies might be incurred to data cache accesses. Fast address generation is an approach proposed to reduce cache access latencies. This paper presents a fast address generator that can eliminate most of the effective address computations by storing computed effective addresses of previous load/store instructions in a dummy register file. Experimental results show that this fast address generator can reduce effective address computations of load and store instructions by about 74% on average for SPECint2000 benchmarks and cut the execution times by 8.5%. Furthermore, when multiple dummy register files are deployed, this fast address generator eliminates over 90% of effective address computations of load and store instructions and improves the average execution times by 9.3%. [Copyright &y& Elsevier]

Abstract: Nowadays, quantum cellular automata (QCA) has been considered as the pioneer technology in next generation computer designs. QCA provides the computer computations at nano level using molecular components as computation units. Although the QCA technology provides smaller chip area and eliminates the spatial constraints than earlier CMOS technology, but different characteristics and design limitations of QCA architectures have led to essential attentions in replacement of traditional structures with QCA ones. Inherent information flow control, limited wire length, and consumed area are of such features and restrictions. In this paper, D flip-flop structure has been considered and we have proposed two new D flip-flop structures which employ the inherent capabilities of QCA in timing and data flow control, rather than ordinary replacement of CMOS elements with equivalent QCA ones. The introduced structures involve small number of cells in contrast to earlier proposed ones in presence of the same or even lower input to output delay. The proposed structures are simulated using the QCADesigner and the validity of them has been proved. [Copyright &y& Elsevier]

Abstract: Modern day applications require use of multi-processor systems for reasons of performance, scalability and power efficiency. As more and more applications are integrated in a single system, mapping and analyzing them on a multi-processor platform becomes a multi-dimensional problem. Each possible set of applications that can be concurrently active leads to a different use-case (also referred to as scenario) that the system has to be verified and tested for. Analyzing the feasibility and resource utilization of all possible use-cases becomes very demanding and often infeasible. Therefore, in this paper, we highlight this issue of being able to analyze applications in isolation while still being able to reason about their overall behavior – also called composability. We make a number of novel observations about how arbitration plays an important role in system behavior. We compare two commonly used arbitration mechanisms, and highlight the properties that are important for such analysis. We conclude that none of these arbitration mechanisms provide the necessary features for analysis. They either suffer from scalability problems, or provide unreasonable estimates about performance, leading to waste of resources and/or undesirable performance. We further propose to use a Resource Manager (RM) to ensure applications meet their performance requirements. The basic functionalities of such a component are introduced. A high-level simulation model is developed to study the performance of RM, and a case study is performed for a system running an H.263 and a JPEG decoder. The case study illustrates at what granularity of control a resource manager can effectively regulate the progress of applications such that they meet their performance requirements. [Copyright &y& Elsevier]

Abstract: The hypercube Q n is one of the most popular networks. In this paper, we first prove that the n-dimensional hypercube is 2n −5 conditional fault-bipancyclic. That is, an injured hypercube with up to 2n −5 faulty links has a cycle of length l for every even 4⩽ l ⩽2 n when each node of the hypercube is incident with at least two healthy links. In addition, if a certain node is incident with less than two healthy links, we show that an injured hypercube contains cycles of all even lengths except hamiltonian cycles with up to 2n −3 faulty links. Furthermore, the above two results are optimal. In conclusion, we find cycles of all possible lengths in injured hypercubes with up to 2n −5 faulty links under all possible fault distributions. [Copyright &y& Elsevier]

Abstract: Nowadays, organizations face with a very high competitiveness and for this reason they have to continuously improve their processes. Two key aspects to be considered in the software processes management in order to promote their improvement are their effective modeling and evaluation. The integrated management of these key aspects is not a trivial task, the huge number and diversity of elements to take into account makes it complex the management of software processes. To ease and effectively support this management, in this paper we propose FMESP: a framework for the integrated management of the modeling and measurement of software processes. FMESP incorporates the conceptual and technological elements necessary to ease the integrated management of the definition and evaluation of software processes. From the measurement perspective of the framework and in order to provide the support for the software process measurement at model level a set of representative measures have been defined and validated. [Copyright &y& Elsevier]

Abstract: Self-organization is bound to greatly affect computer science. The simplicity and yet power of self-organized models will allow researchers to propose efficient solutions to problems never before thought possible to be addressed efficiently. The published works in the field clearly demonstrate the potential of this approach. This paper first reviews a number of interesting self-organization phenomena found in nature, then it discusses their potential applicability in several computer science application scenarios. [Copyright &y& Elsevier]

Abstract: In this paper, we analyze the recurrences from the breakability of the dependence links formed in general multi-statements in a nested loop. The major findings include: (1) A sink variable renaming technique, which can reposition an undesired anti-dependence and/or output-dependence link, is capable of breaking an anti-dependence and/or output-dependence link. (2) For recurrences connected by only true dependences, a dynamic dependence concept and the derived technique are powerful in terms of parallelism exploitation. (3) By the employment of global dependence testing, link-breaking strategy, Tarjan’s depth-first search algorithm, and a topological sorting, an algorithm for resolving a general multi-statement recurrence in a nested loop is proposed. Experiments with benchmark cited from Vector loops showed that among 134 subroutines tested, 3 had their parallelism exploitation amended by our proposed method. That is, our offered algorithm increased the rate of parallelism exploitation of Vector loops by approximately 2.24%. [Copyright &y& Elsevier]

Dynamic branch prediction in high-performance processors is a specific instance of a general time series prediction problem that occurs in many areas of science. Most branch prediction research focuses on two-level adaptive branch prediction techniques, a very specific solution to the branch prediction problem. An alternative approach is to look to other application areas and fields for novel solutions to the problem. In this paper, we examine the application of neural networks to dynamic branch prediction. We retain the first level history register of conventional two-level predictors and replace the second level PHT with a neural network. Two neural networks are considered: a learning vector quantisation network and a backpropagation network. We demonstrate that a neural predictor can achieve misprediction rates comparable to conventional two-level adaptive predictors and suggest that neural predictors merit further investigation. [Copyright &y& Elsevier]

The paper addresses a broad readership in information technology, computer science and related areas, and gives an introduction to fine grain and coarse grain morphware, reconfigurable computing, and its impact on classical computer science and business models. It points out trends driven by microelectronics technology, EDA, and the mind set of data-stream-based computing. [Copyright &y& Elsevier]