Phonetic transcription requires significant time and expert training. Automated, state-of-the-art text-dependent methods still involve substantial pre-training annotation labor and may not generalize to multiple languages. Hallucination of speech amid silence or non-speech noise can also plague these methods, which fall short in real-time applications due to post hoc whole-phrase evaluation. This paper introduces Phonotomizer, a compact, unsupervised, online training approach to automatic, multilingual phonetic segmentation, a critical first stage in transcription. Unlike prior approaches, Phonotomizer trains on raw sound files alone and can modulate computational exactness. Preliminary evaluations on Irish and Twi, two underrepresented languages, exhibit segmentation comparable to current forced alignment technology, reducing acoustic model size and minimizing training epochs.

This paper describes our work in developing a computer vision system that more closely mimics the way the human vision system operates. Autonomous vision systems are crucial for modern vehicle safety, demanding real-time object detection and prioritization without external computational resources. Current systems struggle with this on-board prioritization. This paper presents a novel approach inspired by the human eye and brain, segmenting the video input into foveal and peripheral areas for specialized processing.

IDK Cascades are a framework used to improve time usage within classification tasks. A cascade is comprised of a series of classification models with increasing levels of complexity. A prediction occurs when a single model's computed confidence is above a certain threshold; otherwise, an IDK classification is made, which leads to the next model in the series considering the input. A recent improvement to this scheme is the idea of skipping a model in the case where the prior model's confidence was extremely low. However, this method has inherent issues when predicting whether to skip. This paper improves on the method of skipping certain models by using a Random Forest model trained on multiple parameters, resulting in smart skipping. Unlike the previous threshold skipping approach, the Random Forest's is able to more accurately predict when a skip should occur, leading to larger time savings. Ultimately, we are able to obtain an IDK Cascade utilizing Random Forest skipping that is more computationally efficient than threshold skipping across three datasets.

When routing vehicles through a traffic network, routes are generated to reduce the costs of vehicles traveling through the network with the typical cost function being derived from travel time. What is less considered is the cost derived from vehicle destination-arrival deadlines, while also considering vehicle travel time. In this paper, we explore the extension of a cost function via a vehicle interaction function aimed at reduced vehicle deadline misses by penalizing vehicles that interact with vehicles that miss deadlines. We modify a Dynamic Traffic Assignment implementation in the traffic simulation Simulation Of Urban MObility (SUMO) and test our method on a real-world network. We show that our method is able to outperform Dynamic User Equilibrium and Dynamic System Optimal formulations in tardiness.

In an effort to reduce the runtime of classification algorithms, IDK (I Don’t Know) cascades have been presented as an alternative to current classification models. These structures comprise of a “cascade” of classifiers that only categorizes an input if a classifier outputs a confidence level that exceeds a predetermined threshold. If it does not, it outputs the class “I don’t know” and moves on to the next classifier in the cascade. However, these IDK cascades often reach their worst-case execution time, where classification is only completed by the final classifier. This paper aims to improve the static structure employed by these cascades, deploying a dynamic IDK framework that skips certain classifiers upon meeting specific conditions. A probabilistic analysis run on a previously validated optimal IDK cascade helped us identify these specific conditions, using the outputted confidence level of the first classifier to dictate if a cascade should run its middle classifiers. Ultimately, we generated a dynamic IDK cascade that ran up to 17% faster than its static counterpart.

While the mixed-criticality (MC) approach is naturally suited for multi-processor (or multi-core) systems, scheduling MC tasks on these platforms is much more complex than in the non-MC case. Here, we improve one of the few approaches that explicitly consider criticality information in scheduling the bus access by allowing a more flexible time allocation to the tasks.

Despite the potential of quantum computing for drastically accelerating suitable real-time applications, response time analysis is still required to guarantee that quantum programs running on quantum computers satisfy application-specific timing requirements. This paper describes an inaugural project to determine whether a quantum program running on a quantum computer satisfies the timing constraints of a realtime application, that is, is quantum computing punctual and reliable in this time-sensitive application domain? Can this timing guarantee be formally verified? We leverage the existing work on the functional reactive programming (FRP) model to predict the worst-case response time (WCRT) of fault-tolerant classical computing systems since the timing analysis of re-executions for fault recovery plus transient-faults-induced wasted execution times is similar to determining the response time of FRP tasks. Ongoing work shows that accounting for wasted execution times due to errors in quantum computers resulting from quantum decoherence and state fidelity can be treated similarly and develops a mapping from quantum programs to FRP programs for efficient timing analysis.

A scaled smart city consists of a combination of infrastructure and vehicular agents working in concert to direct traffic throughout the vehicular network at a smaller-thanlife scale. In this paper, we outline our plans for routing to satisfy arrival deadlines, where vehicles are routed with the primary objective of getting somewhere on time. We consider vehicle routing through a traffic sub-network, using a centralized scheme as a guiding traffic assignment agent. We introduce our preliminary implementation of a routing algorithm built on the Selfless Traffic Routing (STR) model and Dynamic User Equilibrium (DUE) to show the viability of such a scheme on a traffic network. We present our experimental results from running this scheme on a real-world traffic network.

There are several optical sensors available that can be integrated into a small satellite for the remote recording of different places on Earth. Colombia in its FACSAT-2 satellite mission has selected a multispectral optical sensor of medium resolution for this task. However, the associated data processing model does not allow the generation of useful products for end users, given the effects that phenomena such as the presence of clouds could cause in 8-band multispectral images captured by FACSAT-2. Therefore, this work proposes the possibility of establishing a real-time system for on-board processing of the data recorded by the satellite optical sensor, taking advantage of the processing resources offered by the embedded computer system in charge of integrating the payloads to the satellite bus and initiating the development of software applications based on artificial intelligence techniques, so that together they can meet the need for autonomously estimating the percentage of cloud coverage in multispectral images prior to the storage and download process, while complying with the restrictions imposed on this type of systems with respect to the time variable.

In this paper, we consider the scheduling of dual-criticality sporadic task systems with arbitrary deadlines using demand bound functions. In dual-criticality systems, tasks are assigned either low-criticality or high-criticality based on assurance needs with associated worst-case execution times. Arbitrary deadlines are those that allow the deadline to be larger than the minimum separation between consecutive task instances. Demand bound functions have been used to successfully schedule dual-criticality task sets for constrained deadlines, i.e., deadlines that are always less than or equal to minimum inter-arrival separation time. We formulate a new demand bound function for a more generalized dual-criticality task system with both constrained and arbitrary deadlines on a preemptive uniprocessor.

In embedded real-time virtualized systems (ERTVS), the ARINC 653 standard specifies a cyclic scheduling policy to guarantee the real-time performance of tasks in multiple Virtual Machines (VMs) residing on shared hardware. Based on this policy, the Regularity-based Resource Partitioning (RRP) model defines an efficient interface specification to hierarchically partition and assign resource slices among VMs. Although this model has received plenty of attention recently, three major pieces remain missing for applying this model in ERTVS. (1) Embedded systems are more sensitive to resource utilization efficiency since this may drastically affect their deployment cost for including additional cores. Therefore, this paper proposes an optimal and an approximate RRP resource scheduler for multi-core platforms. (2) A resource reconfiguration is required when an embedded system has to switch between operating modes, resulting in the current cyclic schedule being replaced by another pre-configured and verified cyclic schedule. This paper formalizes a new One-Hop Reconfiguration (OHR) problem tailored for mode-switch-capable embedded systems and introduces a corresponding optimal solution. (3) No RRP-based toolset is currently available for embedded systems. This paper thus presents an optimized RRP toolset tailored for embedded systems. Numerous experiments are conducted to evaluate the efficacy of this toolset.

A multitude of cloud-native applications take up a significant share of today's world wide web, the majority of which implicitly require soft-real-time guarantees when hosted on servers at various data centers across the globe. With the rapid development of cloud computing and virtualization techniques, many applications have been moved onto cloud and edge platforms that require efficient virtualization techniques. This means a set of applications must be executed on a Virtual Machine (VM) and multiple VMs must be temporally and spatially scheduled on a set of CPUs. Designed to leverage the cloud infrastructure model, many of these cloud-native applications such as media servers strongly demand low data latency and high compute-resource availability, both of which must be predictable. However, state-of-art VM schedulers fail to satisfy these requirements simultaneously. The scheduling of cloud-native applications on VMs and the scheduling of VMs on physical resources (CPUs), collectively need to be real-time in nature as specified by the Hierarchical Real-Time Scheduling (HiRTS) framework. Conforming to the specifications of this framework, the Regularity-based Resource Partitioning (RRP) model has been proposed that introduces the concept of regularity to provide a near-ideal resource supply to all VMs. In this paper, we make the theoretically superior Regularity-based Resource Partitioning (RRP) model ready for prime time by implementing its associated resource partitioning algorithms for the first time ever on the popular x-86 open-source hypervisor Xen, i.e., RRP-Xen. This paper also compares and contrasts the real-time performance of RRP-Xen against contemporary Xen schedulers such as Credit and RTDS. Our contributions include: (1) a novel implementation of the RRP model on Xen's x-86 based hypervisor, thereby providing a test-bed for future researchers; (2) the first-ever multi-core ARINC 653 VM scheduler prototype on Xen; and (3) numerous experiments and theoretical analysis to determine the real-time performance of RRP-Xen under a stringent workload environment.

Detecting heart diseases has been a research interest for centuries. Many of these approaches are based on heartbeat analysis using a stethoscope and some of these are digitally analyzed. In an ordinary system, doctors use an acoustic stethoscope to detect any aberration in the heartbeat and predict atypical conditions of the human heart. One major problem is that the frequency range and intensity of the heart sounds are flat as well as the sound may contain noise. Hence, even a cardiac specialist doctor may encounter difficulties to analyze the heart sound perfectly. This paper describes a new methodology to detect heart diseases by examining heart sounds in real-time. We consider the guts sound as our input data. Our methodology uses a deep learning approach to determine whether a patient has any disease or is healthy. To achieve that, we integrated an electronic stethoscope and a software solution known as a heartbeat audio classifier. Our proposed system solution should be able to differentiate normal heartbeats and heart murmurs with a prediction of probable heart problem type in real-time. We believe our approach assists in reducing the cardiac arrest rate.

Embedded real-time virtualized systems serve a wide range of functions for many important industries. They can encompass multiple independent applications sharing limited computational resources. Many models have been introduced to ensure reliability and energy efficiency for these systems. Hierarchical Real-Time Scheduling (HiRTS) is a framework to enable the sharing of resources. It is used alongside the Regularity-Based Resource Partition model (RRP) to achieve transparent scheduling. A checkpointing system is an effective method to resolve transient faults. However, checkpoint insertions are known to incur high time and energy overheads. This paper proposes a two-state regularity-based checkpointing model within the HiRTS framework. It will ensure fault tolerance when scheduling independent, mixedcriticality real-time task sets on limited resources. By reducing checkpoint insertions before the first fault, the system will achieve higher utilization and less overhead while still ensuring fault tolerance. The simulation-based experiments presented suggest the model could offer a significant increase in utilization and reliability. They will be used as a guideline for future simulations using more complex schedules.

As virtualization becomes increasingly popular, more critical applications that require real-time performance guarantees are deployed on virtualized systems. In such systems, the Hierarchical Real-Time Scheduling (HiRTS) framework divides the scheduling problem into task-level scheduling and resource-level scheduling. Specifically, resource-level scheduling divides a physical resource into multiple resource partitions while task-level scheduling schedules the tasks on each resource partition. Accordingly, the Regularity-based Resource Partitioning (RRP) model offers efficient resource-level scheduling. Despite the availability of adequate resource-level tools, the task-level scheduling based on the RRP model still has a scope for improvements. To extend the applicability of the RRP model under a variety of task workload environments, this paper offers: (1) a more practical schedulability test for independent tasks whose key parameters, i.e., Worst-Case Execution Time (WCET), period and deadline, are non-integral multiples of a time slice; (2) a tuned Earliest Deadline First (EDF) scheduling approach and a corresponding schedulability test for intra-VM dependent tasks; (3) schedulability tests for self-suspended tasks based on Fixed-Relative-Deadline (FRD) scheduling strategies.

The concept of graceful degradation in mixed-criticality real-time systems is still struggling to reach a widely accepted, global view. Numerous results have emerged in this field during the last years, but there is still a lot of work to do. This paper comes with an addition to a recent work [2] in the field of scheduling in semi-clairvoyant systems: it introduces a new criterion for determining which low criticality jobs should be switched upon a system criticality mode transition.

Images are an important part of digital communication in this era. The optimization of image file size and algorithms for image transfer are vital to ensure quality of service levels and expected time requirements for services. This paper describes and evaluates a combination of file reduction and scheduling techniques from a system design level to ensure that image transfer timing constraints are satisfied.

Real-time embedded systems with safety-critical functions must often share a limited number of computational resources. Scheduling models within the Hierarchical Real-Time Scheduling (HiRTS) framework allow applications to share resources in an efficient manner. The Regularity-Based Resource Partition (RRP) model offers an efficient way to schedule resource partitions, ensuring transparent task scheduling. A model within this framework can manage resource distribution in real-time embedded systems, ensuring fault tolerance through a checkpointing system. However, checkpoint insertions are known to incur high time and energy overheads. This paper proposes the use of a Two-State checkpointing scheme in conjunction with the fault-tolerant hierarchical RRP model. By reducing the number of checkpoints during fault-free states, we can reduce time and energy overheads while still ensuring fault tolerance in worst-case fault scenarios. We outline our plan to construct a model that can offer low-overhead solution to transient faults in embedded real-time systems. We do so with the intent to build upon this model and eventually test it through simulation.

Many safety-critical applications employ embedded real-time systems where both timing and fault tolerance requirements must be continually satisfied. The Regularity-based Resource Partition Model (RRP), which is known for its code level independence between resource level and task level, is used to schedule resource partitions in virtualized real-time systems. This paper presents a fault tolerance model for Regularity-based Real-Time Virtual Resources to recover from transient hardware faults without modifying user applications. The proposed framework consists of a checkpointing mechanism called Fault-Tolerant RRP with a checkpointing partition followed by a redundancy partition prepared for re-execution to satisfy task deadlines despite the occurrence of faults. The frequency of checkpoints and the number of time slices in the redundancy partition are parameterized by the fault rate of the hardware resource and the sum of the availability factors of the original partition sets. Extensive theoretical analysis and simulation-based experiments show the effectiveness of the proposed framework while incurring minimal overhead.

The specification, design, prototyping, analysis, implementation, information management, verification, privacy and security guarantees, safety assurance, and maintenance of cyber-physical systems (CPS) are extremely complex, owing to the multitude of operating systems, software components, hardware platforms, communication infrastructures, sensors and activators, human-machine interfaces, and numerous intertwined feedback loops. This paper describes a project to simplify all these life-cycle phases of developing and maintaining CPS by introducing Real-Time Virtual Resources (RTVR). RTVR forms a virtual layer between application software components and physical resources consisting of hardware platforms, communication infrastructures, and sensors and activators so that the software components can be implemented without knowledge of the details of the physical resources and thus can be ported from one physical resource into another with ease. Such open systems make it easy to add and remove software applications and reduce implementation cost when compared to systems which physically assign distinct computing resources to run different applications. However, most existing virtualization schemes significantly under-utilize the underlying physical resources in order to maintain the schedulability of real-time tasks as if they were scheduled on dedicated physical resources. Also, these schemes are not transparent to the software applications in that they need to be aware of each other and modification of the software may be necessary. Our proposed RTVR based on the Regularity-based Resource Partition (RRP) Model overcomes the above shortcomings, making it a true contender in simplifying all phases of CPS development and maintenance. This paper outlines the first of four project tasks to be performed: the specification, design, prototyping, analysis, implementation, verification, and maintenance of CPS with RTVR.

With increasing traffic in urban areas, it is crucial to examine strategies to reduce traffic network congestion. Popular navigation policies currently tend to select the fastest path available for each vehicle. However, a top-down approach to navigation, which considers the traffic network as a whole, offers several speedup possibilities. Minimizing the average travel time of all vehicles in the network with respect to their separate travel deadlines improves traffic throughput. Because such a strategy does not guarantee an optimal navigation route for individual vehicles, we refer to it as a "selfless" policy and based on this observation we propose the Selfless Traffic Routing (STR) model. Hence, we propose a test bed based on Simulation of Urban MObility (SUMO) that can evaluate the performance of a traffic routing policy based on the average travel time of all vehicle agents in a given traffic grid. Continuously calculating optimal actions for multiple agents in real-time is computationally complex. We therefore introduce a value-based reinforcement learning strategy to achieve the benefits offered by a selfless traffic routing model. We explore how this approach can potentially achieve an optimal balance between action quality and the real-time performance of each decision.

The rapid advancement and use of Cyber-Physical Systems (CPS) has brought about the necessity for enhancing security and attack identification in such systems to counter malicious attacks. One example of an attack on a CPS involves the Stuxnet worm which caused significant damage to both the control system and the physical world. Such events have created a need for a robust security system in order identify and prevent attacks. This paper focuses on the detection of integrity attacks, such as replay attacks, on Linear Time Invariant systems. More specifically, it considers the feasibility of combining a chi-squared failure detector and a moving target approach to identify malicious sensors.

The goal of this research is to reduce the maximum response time of tasks within a task set by introducing offsets. In this research, we propose an iterative method to determine the best offset for a given task. This method iterates through a set of tasks starting with the task having the highest priority to determine which offset gives the shortest maximum response time. Reducing the maximum response time can lead to a more efficient system and avoids over-provisioning of hardware resources.

One of the more complex issues facing natural language processing (NLP) is how to deal with overlapped speech, i.e., when two or more speakers interfere with or talk over each other, and the more general case of co-channel speech, i.e., when two or more speakers are present in an audio stream regardless of interference. Frequently, one speaker is selected as a primary speaker for the purpose of analysis with other speakers relegated to the category of interfering speakers. Despite the breadth of research into overlapped speech detection, few endeavors have been made into preserving the speech of so-called interfering speakers. A compelling case can be made for a more comprehensive analysis of co-channel speech in the fields of computational linguistics, accessibility automation, and entertainment, particularly under real-time constraints. Currently available open-source audio libraries, while technically capable of supporting such research endeavors, are cumbersome to work with. To this end, the work introduces the Adaptive Real-Time Imprecise Computation (ARTIC) pipeline for audio analysis, a simple but flexible approach to stream processing that tracks computation times and deadlines for the various pipeline stages and affords the user the ability to specify automatic precision reductions to avoid projected deadline misses as well as automatic precision increases to combat underutilization. A proof of concept is tested with the intent to build upon this groundwork for a more comprehensive project having the goal of multi-speaker interference detection and eventually speaker separation.

In this paper, we describe how Shannon's information theory is used to develop the Simplified Information-Theoretic Scheduling algorithm for Real-time Systems (SITSA-RT), and we explain the mechanism used by this algorithm to reduce the number of job migrations in real-time systems implemented in a multiprocessor platform. We present a performance comparison of the proposed algorithm with different multiprocessor scheduling algorithms for synthetic and real-case task sets. The results of the performance comparison for the synthetic task sets case show that outperforms all the studied EDF-based (up to 41.65%) and P-Fair based algorithms (up to 93.22%) in terms of the reduction of the number of job migrations while offering a similar performance in terms of the number of preemptions, the number of tasks migrations, and deadline miss ratio. These results show that as the utilization per task set and the number of processors increase, SITSA-RT is able to improve its performance in terms of the number of migrations. The results from the real-case task set based on NASA's X-38 avionics architecture show that for the scheduler execution time, MLLF improves the performance of SITSA-RT by 5.96% and SITSA-RT improves the performance of LLF by 19%, and from the memory requirements we found that MLLF usage is 13.48% lower than SITSA-RT, and SITSA-RT usage is 52.97% lower than LLF.

Processing and analyzing big data sets updated in real time in an increasing number of applications such as severe weather prediction and particle-physics experiments require the computational power of extreme-scale high-performance computing (HPC) systems. To address the scheduling of massive task/thread sets on these extreme-scale systems, current strategies rely on improving centralized, distributed, and parallel scheduling algorithms as well as virtualization developed for HPC systems which aim to reduce the makespan and balance the load among the computing nodes in these systems. However, these HPC schedulers provide no guarantees on meeting timing constraints such as deadlines that are required in an increasing number of these real-time science workflows. This paper describes a new project which departs from this established trend of best-effort scheduling of large-scale HPC Message Passing Interface (MPI) tasks and ensemble workloads found in fine-grain many-task computing (MTC) applications. The new approach brings real-time scheduling to address the demands of real-time science workloads. This new framework abstracts information about the tasks or threads, and continuously dispatch this workload to meet deadlines and other timing constraints associated with individual tasks or groups of tasks in extreme-scale HPC systems to reduce execution time and energy consumption. This paper introduces deadline-based scheduling in the tasking programming model.

Minimal schedulability interval is one of the important considerations of both research motivation and practice stage. In this paper, we investigate the problem of finding a starting time point of the minimal schedulability interval for fixed priority independent periodic real-time preemptive tasks with arbitrary given release offsets (phasing). A linked list-based method is proposed for solving the problem. Each node in the linked list represents a pending-less busy period. Analysis and experimental results show that the linked list-based method outperforms the current best acyclic-idle-slot-based one.

Functional Reactive Programming (FRP) provides an elegant way to express computation in domains such as interactive animations, robotics, computer vision, user interfaces, and simulation. Priority-based (preemptive) FRP (P-FRP), a variant of FRP with more real-time characteristics, demands research in its scheduling and timing analysis. Different from the classic preemptive model, in a P-FRP system, when a task is preempted, all changes made by the task are discarded and after higher priority tasks complete their execution the preempted task will restart from the beginning (abort-and-restart). P-FRP is thus able to capture changes of the task in time and provides an option other than the classic preemptive model in certain scenarios. In the P-FRP model, previous studies use the largest execution time of a task for all its restarted jobs. In practice, however, when considering the changing/unchanging inputs/outputs of the task or the memory effects such as cache-hit in loading code and data, the restarted jobs likely consume less time than its largest execution time. In this paper, for the first time we present a multi-mode P-FRP task framework and two particular scenarios for the framework that are able to reflect such effects and then improve the performance of a developing commercial software platform. We show that the multi-mode task P-FRP system has significant schedulability improvements over the original P-FRP model.

Most Hierarchical Real-time Scheduling (HiRTS) techniques have focused on temporal resource partitions in which time units are periodically distributed. Although such periodic partitions could provide great flexibility for the resource-level scheduling, engineers face significant obstacles when trying to determine the schedulability of real-time tasks running on them. The main reason is that periodic partitions fail to effectively bound the difference between the ideal and the actual resource allocation. To solve this problem, some researchers introduced the Regular Partition, a type of temporal resource partition that is almost evenly distributed. Recent research has shown that it achieves maximal transparency for task scheduling—some classical real-time scheduling problems on a regular partition can be easily transformed into equivalent problems on a dedicated single resource. However, the resource partitioning problem for regular partitions is much more complicated than the one for periodic partitions. Based on a practical two-layer HiRTS platform, this article introduces MulZ (Multiple Z-seqences), which is the first to solve this problem with a partitioned scheduling strategy. By using a more complicated approximation methodology, our experimental results show that MulZ outperforms the current best global scheduling algorithm on this problem. After that, it compares the overall performance of the periodic partition and the regular partition. We conclude that the regular partition is a better choice for the integration of real-time applications.

Summary form only given. The purpose of this paper is to analyze the performance of the Highest Entropy First (HEF) scheduling algorithm for real-time tasks. The contributions of this paper are: · Generate multiple task sets by implementing the programs from the Seoul National University (SNU) real-time benchmark in Wind River Workbench 3.3 to calculate the WCET and generating the periods by using a linear programming solution aiming to maximize the utilization of the system based on a predefined hyper-period. We implemented the SNU programs (sqrt.c, fibcall.c, crc.c, minver.c and select.c) on a server with an Intel i7-3770 processor running at 3.4 GHz, with 16 GB of RAM and 2 TB hard drive using Wind River Workbench 3.3 to calculate the worst case execution time (WCET). We run each program 100 times to average the results. We created 4 task sets with 2, 3, 4, and 5 tasks respectively. For each task set we used 100 ms as the hyper-period to calculate the periods of the tasks. We implemented a system with implicit deadlines. · Measure the performance of HEF algorithm to schedule real-time tasks using as metrics the number of context switches and deadline-miss ratio. The results from the preliminary performance evaluation show that the number of context switches is directly proportional to the number of tasks in the task set. For the deadline-miss ratio, HEF was able to schedule all the task sets without missing any deadline. Further analysis must be made to confirm that the deadline-miss ratio depends on the utilization of the system (U ≤ 1 = no deadline misses). The HEF algorithm has some similarities with the earliest deadline first algorithm (EDF), therefore we propose as future work to compare the performance of HEF against EDF using the task sets generated by the methodology proposed in this paper.

Summary form only given. In the context of fixed priority preemptive real-time systems, for n periodic/sporadic tasks that comply with a restrictive system model and that have implicit deadlines the Rate-Monotonic (RM) scheduling is optimal. When these tasks are released simultaneously the time required by the first job of each task defines its response time. It thus needs only to make response time analysis or conduct exact schedulability test within a time length no more than the maximum task period (Tn) for RM scheduling, and these tests are thus known to be pseudo-polynomial in time complexity. Although the response time computation for RM schedules of implicit-deadline task-systems has been proved to be an NPhard problem, the scale of many commercial systems is such that pseudo-polynomial exact tests can be used, and to achieve more efficient exact tests such as for online response time analysis (RTA) is one of important considerations of both research motivation and practice stage. The innovative aspect of our solution is that we use a linked list for representing the schedule in the exact response-time schedulability test, referred to as the LList-based test. A busy period in the schedule is represented by a linked list node, recording the starting time and the end time of a busy period, and the pointer to the next node. The simulation is performed task per task in the priority order (from 1 to n), and, when the starting time or the end time of a busy period is the same as that of other busy periods, then the two nodes are merged into one node to represent a longer busy period. For improving the efficiency, memory allocation and recycle for each node are also performed in the user space. The time complexity of the LList-based test is O(N) where N is the total number of jobs within the time length Tn, while the total number of nodes in the linked list is no more than N - n + 1 in the worst case. Our experiments show that the LList-based exact test is a better candidate in exact response-time tests when task periods span no more than three orders of magnitude, since it outperforms the current best exact tests in this scenario, and the needed memory space is also affordable.

Summary form only given. Multiprocessor real-time scheduling algorithms may follow a partitioned or global approach or some hybrid of the two, called semi-partitioning. Semi-partitioned real-time scheduling algorithms extend partitioned ones by allowing a subset of tasks to migrate. Given the goal of “less overhead”, it is desirable for such strategy to be boundary-limited, and allow a migrating task to migrate only between successive invocations (job boundaries). Non-boundary-limited schedulers allow jobs to migrate, which can be expensive in practice, if jobs maintain much cached state. Previously proposed semi-partitioned algorithms for soft real-time (SRT) tasks such as EDF-fm and EDF-os, have two phases: an offline assignment phase, where tasks are assigned to processors and fixed tasks (which do not migrate) are distinguished from migrating ones; and an online execution phase. In their execution phase, rules that extend EDF scheduling are used. These strategies aim to minimize tardiness. In this paper, we propose a new online reward-based semi-partitioning approach to schedule periodic soft real-time tasks in homogeneous multiprocessor systems. We use an online choice of two approximation algorithms, Greedy and Load-Balancing, for partitioning, which provides an optimized usage of processing time. In this method, no prior information is needed. Hence, there is no offline phase. Our objective is to enhance the QoS by minimizing tardiness and maximizing the total reward obtained by completed tasks in minimum makespan. Therefore, we allow different jobs of any task get assigned to different processors (migration at job boundaries) based on their reward-based priorities and workload of the processors. This method can also extend to direct SRT systems with mixed set of tasks (aperiodic, sporadic and periodic) by defining their deadline accordingly. Many real-time applications can benefit from this solution including but not limited to video streaming servers, multi-player video games, mobile online banking and medical monitoring systems.

Summary form only given. Functional Reactive Programming (FRP) is playing and potentially going to play a more important role in real-time systems. Priority-based (preemptive) FRP (P-FRP), a variant of FRP with more real-time characteristics, demands more research in its scheduling and timing analysis. In a P-FRP system, similar to a classic preemptive system, a higher priority task can preempt a lower-priority one and make the latter abort. The lower-priority task will restart after the higher priority tasks complete their execution. However, unlike the classic preemptive model, when a task aborts, all the changes made by the task are discarded (Abort and Restart). In previous studies, the value of Worst Case Execution Time (WCET) of a task is used for all its restarted tasks. However, in practice restarted tasks likely consume less time than WCET when considering the memory effect such as cache-hit in loading code and data. Here we consider a typical task life cycle without being interrupted (cold started task): (1) code is loaded from hard drive and data is loaded from main memory; (2) computation is done by processor(s); (3) results are committed to main memory. In the P-FRP model, the time spent in phase (2) and (3) is wasted when a task is aborted, however, since the existence of memory hierarchy, the time spent in phase (1) can be less when a task is restarted, for example, the task code is still in cache and does not need to be read from slow main memory again. This memory effect is not considered in previous studies of P-FRP systems. In this paper, we present our preliminary memory-aware P-FRP task response time analysis and experimental results. Our ongoing research is to present more theoretical response time analysis and priority assignment research in the memory-aware P-FRP task scheduling. And since the execution time difference is likely related to data placement/locality, we will address this difference in our multi-core P-FRP task scheduling research too.

Priority-based Functional Reactive Programming (P-FRP) is a new variant of FRP to model reactive applications in real-time systems. In P-FRP, when the currently running task is preempted by an arriving higher-priority task, the lower-priority running task is aborted and the higher-priority task will execute. The lower-priority task restarts when the higher-priority one completes. However, unlike the preemptive model, when a task aborts, all the changes made by this task are discarded. That is to say, when an aborted ask restarts, it should execute from the beginning. In order to provide a realistic Worst-Case Response Time (WCRT) of the tasks in P-FRP, it is therefore mandatory to derive a realistic Worst Case Execution Time (WCET) of each task. Previous studies have ignored memory latency in the derivation of the WCRT, making the resulting estimate inaccurate and unrealistic. Furthermore, these studies have also assumed that the WCET of each task is known a priori. In this paper, we introduce a scratchpad memory (SPM)-based platform for executing P-FRP tasks and an approach to determine the WCET of the tasks by considering the memory cost of the aborted tasks. We first compute the WCET of a task in a P-FRP system, and then calculate the memory penalty caused by preemption. In the next step, we derive the WCRT of the task sets in P-FRP by considering memory latency in the proposed platform. Experimental results from the derivations of the WCET and WCRT using task sets from the SNU real-time benchmarks and randomly generated tasks are presented to validate this approach.

The Hierarchical Real-Time Scheduling (HiRTS) technique helps improve overall resource utilization in real-time embedded systems. With HiRTS, a computation resource is divided into a group of temporal resource partitions, each of which accommodates multiple real-time tasks. Besides the computation resource partitioning problem, real-time task scheduling on resource partitions is also a major problem of HiRTS. The existing scheduling techniques for dedicated resources, like schedulability tests and utilization bounds, are unable to work without changes on temporal resource partitions in most cases. In this paper, we show how to achieve maximal transparency for task scheduling on Regular Partitions, a type of resource partition introduced by the Regularity-based Resource Partition (RRP) Model. We show that several classes of real-time scheduling problems on a regular partition can be transformed into equivalent problems on a dedicated single resource, such that comprehensive single-resource scheduling techniques provide optimal solutions. Furthermore, this transformation method could be applied to different types of real-time tasks such as periodic tasks, sporadic tasks and aperiodic tasks.

We present DwarfCode, a performance prediction tool for MPI applications on diverse computing platforms. The goal is to accurately predict the running time of applications for task scheduling and job migration. First, DwarfCode collects the execution traces to record the computing and communication events. Then, it merges the traces from different processes into a single trace. After that, DwarfCode identifies and compresses the repeating patterns in the final trace to shrink the size of the events. Finally, a dwarf code is generated to mimic the original program behavior. This smaller running benchmark is replayed in the target platform to predict the performance of the original application. In order to generate such a benchmark, two major challenges are to reduce the time complexity of trace merging and repeat compression algorithms. We propose an O(mpn) trace merging algorithm to combine the traces generated by separate MPI processes, where m denotes the upper bound of tracing distance, p denotes the number of processes, and n denotes the maximum of event numbers of all the traces. More importantly, we put forward a novel repeat compression algorithm, whose time complexity is O(nlogn). Experimental results show that DwarfCode can accurately predict the running time of MPI applications. The error rate is below 10 percent for compute and communication intensive applications. This toolkit has been released for free download as a GNU General Public License v3 software.

This paper studies the schedulability of real-time tasks in the Priority-based Functional Reactive Programming (P-FRP) model under fixed priority scheduling, one of the influential scheduling policies. Since the abort-and-restart execution paradigm of the P-FRP model is different from that of the classic pre-emptive model, the schedulability analysis for P-FRP tasks under fixed priority scheduling differs widely. In P-FRP, for a synchronous n-task set under fixed priority scheduling, the least common multiple (LCM) of all n task periods is the typical length of a testing interval for an exact (necessary and sufficient) schedulability test. In this paper, we propose and prove an optimal simulation based exact schedulability test in the P-FRP model under fixed priority scheduling for a given priority order, covering scenarios from synchronous task release to asynchronous task release with the initial busy condition, and from implicit deadlines to constrained deadlines. The length of a testing interval for the exact test is the LCM of the first n-1 task periods and its optimality is proved.

The purpose of this paper is to present the mathematical background for using entropy in real-time scheduling as well as the relationship between entropy and utilization. We present a new scheduling algorithm based on entropy to schedule tasks in real-time systems. The goal is to minimize the uncertainty of the scheduling problem by executing the task with the highest entropy first without missing any deadline. The uncertainty measurement is based on the probability of the execution of a task during the hyper-period. This study aims to present entropy as a new parameter that can be used by researchers in different real-time systems fields.

In real-time systems, FRP (Functional Reactive Programming) is playing and potentially going to play a more important role. Priority-based (preemptive) FRP (P-FRP), a variant of FRP with more real-time characteristics, demands more research in its scheduling and timing analysis. Its abort-andrestart nature indicates that reducing preemptions can be critical for improving system performance. In this paper, we present a non-work conserving scheduling model, Deferred Start, to reduce certain preemptions. Experiments show the improvement on schedulability and task response time.

Electrophoretic displays (EPDs) and organic light emitting diode (OLEDs) are two key technologies used in mobile de-vices. In this paper, we propose the design of an integrated hybrid display combining a transparent OLED (TOLED) and a low power EPD, which is adaptive to show contents of a frame partially on either the TOLED or the EPD. A windows-based predictive model and a calibration algorithm on TOLED are introduced to decide how frame contents can be split between the two displays for achieving the best tradeoff between power reduction and user experiences. A simulation environment that can estimate both the energy consumption and optical properties of the proposed hybrid display is set up based on actual physical measurements. Simulation results show that the predictive model can make right decisions on choosing proper displays in over 90% of the test cases, and this new display design can save over 70% power under many mobile application contexts and still sup-port contents that require fast update rates.

The Small Aircraft Transportation System (SATS) protocol, developed at NASA, aims to increase air transportation access for smaller communities and improve the transportation of people, services, and goods by a more effective use of over 5,000 small public airports in the United States. By using model checking and I/O automata, a number of different groups have verified many of the operational properties of SATS. However, none of the published work considers the timing constraints of the protocol, delegating instead to the pilot the responsibility for providing appropriate delays and separation assurance among events. In this paper, we formally specify the delays and the deadlines for the landing component of the protocol for simultaneous approaches of several small aircraft. This helps increase pilot safety for landing in these small airports. Linear Real-Time Logic (LRTL), a subclass of Real-Time Logic, and its associated toolset are utilized to analyze and formally verify the timing constraints of the landing component of SATS. In addition, an algorithm for debugging a subset of LRTL models is proposed.

Hierarchical scheduling is a hot topic in realtime systems. In a hierarchical real-time system, the resource partition is the intermediate level between physical resources and real-time tasks. A resource partition operates on the shared physical resources at a fraction of the rate, and serves as a scheduling interface between the lower-level real-time tasks and the shared physical resources. Thus a key problem is how to define this scheduling interface on resource partitions. Regularity-bounded methodology is one important type of resource partitioning algorithms. This paper extends Mok and Feng's Regularity-based Resource Partition Model from a single-resource platform to a uniform multiresource platform. We present a resource partitioning algorithm called AAF-Multi Scheduling for solving the time slice overlap problem on a multiresource platform without violating the schedulability bound given by Feng on a single-resource platform. AAF-Multi is a global scheduling algorithm with O(Ω · log Ω) time complexity (Ω = resource amount × hyper period), where hyper period is the least common multiple of the periods of the resource partitions.

As a hierarchical real-time system framework, the Regularity-based Resource Partition Model allocates physical resources in time intervals determined by integral numbers of a time unit to tasks in different applications. A Regularity-based Resource Partition is characterized by its regularity and availability factor. An important problem is how to schedule a group of resource partitions with the specification of their regularities and availability factors. Mok and Feng have provided the AAF-Single algorithm which works only on a single-resource platform. Li and Cheng have recently extended AAF-Single to AAF-Multi for multiresource platforms without violating the schedulability bound given by Feng. However, the resource utilization of these two algorithms could be significantly improved. This paper is dedicated to developing optimized resource partitioning algorithms for the Regularity-base Resource Partition Model. We first decompose the resource partitioning problem into two sub problems, and invoke the Pfair algorithm to solve the first sub problem. Then we introduce a category of approximation algorithms called Static Approximation Algorithms (SAA) to solve the second sub problem. An SAA adjusts the availability factors of the resource partitions with a specific boundary sequence. We prove that the schedulability bound of any feasible SAA is at most 0.5. Furthermore, we develop an optimal SAA called Magic7. Simulation shows that Magic7-enhanced algorithms improve the resource utilization by 10% or more.

Functional Reactive Programming (FRP) is a declarative approach to modeling and building reactive systems. Priority-based FRP (P-FRP) has recently been introduced as a FRP formalism that guarantees real-time response. P-FRP guarantees that when a higher priority task is released, the system will immediately preempt any executing lower-priority tasks. To maintain guarantees of state-less execution offered by the functional programming model, P-FRP implements a transactional nature of execution. Each higher priority event in P-FRP can abort a lower priority task forcing it to restart. Existing work on partitioning tasks in multi-processor systems have been focused on the classical preemptive model of execution1. However, due do its transactional nature, the schedulability tests used in the partitioning algorithms for the preemptive model, cannot be applied 'as is' to the P-FRP execution model. While multiprocessor response time analysis of P-FRP has been done in previous work, partitioning schemes for tasks in multi-processor systems have not been presented yet. In this paper, we present an exact schedulability test for P-FRP and use it in two existing first-fit partitioning schemes. We also introduce a new first-fit partitioning scheme based on the processing time of tasks, which yields better results than the other two schemes. We also show that the number of processors required to schedule tasks in P-FRP are more than or equal to the number of processors required to schedule the same in the preemptive model.

Priority-based Functional Reactive Programming (P-FRP) is a new functional programming formalism for developing safety-critical embedded systems. P-FRP allows static priority assignment and guarantees real-time response by preempting lower priority tasks. Due to the state-less nature of functional programs, preempted tasks in P-FRP are aborted and have to restart after the higher priority tasks have completed execution. Since the execution semantics of P-FRP are different from the classical preemptive model of execution, existing utilization based sufficient conditions cannot be applied. In this paper, we derive a new utilization based sufficient schedulability condition for P-FRP, and validate it using experimental task sets.

Schedulability analysis models in embedded and real-time systems are experimentally validated using synthetic task sets, which are generated using random or pseudo-random selection algorithms. Validation of these schedulability models generally requires analyzing release of all jobs of tasks within a defined interval called the feasibility interval of the task set. The length of this interval is dependent on the hyper-period, which is the least common multiple of task periods. Hence, the time taken in experimental validations is directly proportional to the value of hyper-period, apart from the number and size of task sets. Currently, if tasks period values with low hyper-period are required, the only way to generate them is using manual or ad-hoc methods. In this paper, we present a structured method of selecting task period values from within a user-specified bounded range such that the hyper-period values of these task sets is minimized. Formula to compute maximum number of task sets of different sizes that can be generated is also derived. Finally, comparisons of hyper-period values generated from a bounded range using random selection and our method are presented.

Medical sensor devices, such as ECG, handle life-critical information, which have to be transmitted to remote monitoring servers in a timely manner. We propose a new approach to improve QoS of ECG data transmission when these devices are deployed in home or healthcare facility supported by EDCA-based WLANs. First, we analyze real-time data from wireless ECG devices to investigate their QoS requirements, and convert them to a real-time model with (m, k)'-firm deadlines. Second, we propose a new admission control mechanism to protect real-time ECG data transmission from other traffic initiating from non-medical applications. Finally, we propose our solution to cope with potential adverse effects from co-existence with the legacy DCF-based wireless stations.

A new, purely functional model of computation, called Priority-based Functional Reactive Programming (P-FRP), has been introduced as a new paradigm for building real-time software. P-FRP allows assignment of static priorities to tasks and guarantees that, when a higher priority task is released, the system will immediately preempt any lower-priority tasks that may be executing at the time. This execution model is different from the classical preemptive model of real-time systems due to the abort nature of preempted tasks. Methods developed for determining actual response time in the preemptive model are not guaranteed to work in P-FRP. In previous work, the gap-enumeration technique has been presented as a viable alternative to simulations for computing actual response time in P-FRP. Unfortunately, this method is difficult to implement due to its use of a Red-Black tree which is not available as a native function in programming languages. Also this method requires a complex logic loop for finding idle periods. In this paper, we present another technique using game-board which is simple to implement and uses native data structures. However, this simplicity comes at a performance cost which has also been analyzed in this paper.

In real-time systems research, validations are usually performed by executing synthetically generated tasks through programmatic implementations of derived algorithms or theoretical results. For every new result, real-time researchers have to develop systems, several times from scratch, for generating task sets as well as implementing their derivations. Another issue arises when the results are submitted for peer review. Reviewers only have access to results in the form of numerical values given in the paper, and have no easy way of validating the results themselves. To solve these two issues, we present a new extensible system for real-time task generation and simulation. Using modern software engineering principles of object and reflection-oriented programming, we show how real-time analysis can be partitioned into sub-systems, where each such subsystem can be implemented as a run-time 'plug-in' which can be independently developed by different research groups. This technique is intended to save real-time researchers the significant amount of time spent in result validation, as well as allow reviewers easy access to the experimental setup of the submitted paper for a more efficient review process.

Functional Reactive Programming (FRP) is a resource aware declarative approach for modeling and building safety-critical embedded systems. Recently, Priority-based FRP (P-FRP) was introduced as a formalism that guarantees real-time response. Due to the state-less nature of execution of functional programs, P-FRP implements a transactional nature of execution where preempted lower priority tasks are aborted. This makes the response time of a lower priority task completely dependent on the execution pattern of higher priority tasks. The feasibility interval in the classical preemptive model of real-time systems is known and is dependent on the least common multiple (LCM) of task periods. However, since the abort nature of preemption can induce side-effects on the execution of lower priority tasks, it has been unknown to date if the feasibility in P-FRP is also dependent on the LCM. In this paper, we rigorously prove that these side-effects of preemption are bounded within the LCM and formally derive a value of the feasibility interval in P-FRP. This value of feasibility interval is vital for more robust schedulability analysis of the P-FRP execution model.

Transactional Memory (TM) is a mechanism to control access to shared resources in memory. Though originally implemented in hardware, software implementations of TM are now available as library extensions in major programming language. Lately, variants of software transactional memory (STM) with real-time support have been presented. As real-time STM begins to be increasingly used in commercial embedded systems, a good understanding of their temporal properties for ascertaining real-time guarantees is required. Unlike the classical models of preemptive or non- preemptive execution, in STM higher priority tasks can induce an abort cost in addition to the interference cost on preempted lower priority tasks. Due to the abort cost, several existing approaches developed for the classical model cannot be used to ascertain real-time guarantees in STM. In this paper, we convert the abort costs induced by higher priority tasks into new phantom tasks and transform the transactional execution model of STM into a pessimistic preemptive model. An existing iterative method to compute response time is then applied to determine schedulability. This approach is utilized to derive a polynomial time sufficient schedulability test for both the lazy and eager conflict detection polices of STM. Experiment results to validate the sufficient test and analyze its coverage are presented.

Software Transactional Memory (STM) is a mechanism for controlling access to shared resources in memory using an abort-restart preemption model for tasks which share data objects. This execution model of STM is different from the classical preemptive or non-preemptive models and currently the only method to determine schedulability is through an exhaustive search through the state space of all release scenarios of higher priority tasks. The existing method is costly and scales exponentially with the number of tasks making its use limited in practical situations. Timed Automata has been proven as an expressive formalism for time based systems. This paper presents a methodology for developing Timed Automata encodings for the schedulability analysis of STM systems. We validate our models using the model checker UPPAAL, and show that Timed Automata offers an efficient alternative for schedulability analysis in real-time STM.

Functional Reactive Programming (FRP) is a declarative approach to modeling and building reactive systems. Priority-based FRP (P-FRP) is a formalism of FRP that guarantees real-time response. Unlike the classical preemptive model of real-time systems, preempted tasks in P- FRP are aborted and have to restart when higher priority tasks have completed. Due to this abort-restart of nature of preemption, there is no single critical instant of release that leads to Worst-Case Response Time (WCRT) of lower priority P-FRP tasks. At this time, the only method for determining the WCRT is through an exhaustive enumeration of all release offsets of higher priority tasks between the release and deadline of the lower priority task. This makes the computational cost of WCRT dependent on the deadline of a task, and when such deadlines are large the computational costs of this technique make it infeasible even for small task sets. In this paper, we show that the release offsets of higher priority tasks have a lower and upper bound and present techniques to derive these bounds. By enumerating only those release offsets while lie within our derived bounds the number of release scenarios that have to be enumerated is significantly reduced. This leads to lower computational costs and makes determination of the WCRT in P-FRP a practically feasible proposition.

In the past decades, many algorithms with the goal of achieving energy efficiency have been proposed for scheduling real-time tasks. Due to a lack of a unified testing framework, most of them were evaluated via simulations under their own experimental scenarios. However, finding their performance in real processors is essential if these algorithms are to be used in practice. In this paper, we design a unified framework to evaluate power-aware scheduling algorithms based on a real Intel PXA255 XScale processor, and present a case study to compare several key algorithms using DVS/Shut-Down. The energy efficiency and the quantitative difference in their performance as well as the practical issues found in the implementation of these algorithms are discussed. Our experiments show a gap between the theoretical results and the real results. Our framework not only gives researchers a tool to evaluate their system designs, but also helps them to bridge this gap in their future works.

Tasks' scheduling has always been a central problem in the embedded real-time systems community. As in general the scheduling problem is NP-hard, researchers have been looking for efficient heuristics to solve the scheduling problem in polynomial time. One of the most important scheduling strategies is the Earliest Deadline First (EDF). It is known that EDF is optimal for uniprocessor platforms for many cases, such as: non-preemptive synchronous tasks(i.e., all tasks have the same starting time and cannot be interrupted), and preemptive asynchronous tasks (i.e., the tasks may be interrupted and may have arbitrary starting time). However, Mok showed that EDF is not optimal in multiprocessor platforms. In fact, for the multiprocessor platforms, the scheduling problem is NP-complete in most of the cases where the corresponding scheduling problem can be solved by a polynomial-time algorithm for uniprocessor platforms. Coffman and Graham identified a class of tasks for which the scheduling problem can be solved by a polynomial time algorithm, that is, two-processor platform, no resources, arbitrary partial order relations, and every task is nonpreemptive and has a unit computation time. Our paper introduces a new non-trivial and practical subclass of tasks, called urgent tasks. Briefly, a task is urgent if it is executed right after it is ready or it can only wait one unit time after it is ready. Practical examples of embedded real time systems dealing with urgent tasks are all modern building alarm systems, as these include urgent tasks such as `checking for intruders', `sending a warning signal to the security office',`informing the building's owner about a potential intrusion', and so on. By using propositional logic, we prove a new result in schedulability theory, namely that the scheduling problem for asynchronous and preemptive urgent tasks can be solved in polynomial time.

Real-time systems are one of the fields of computing where major benefits are expected from the increasing availability of multiprocessor technology. Heterogeneous computing environments, which utilize different high-performance machines interconnected via a high speed communication system, are well suited to the large, computation intensive, real-time or non-real-time applications. Nowadays, many of the systems in these environments are powered by rechargeable batteries. Scheduling real-time tasks on these rechargeable systems is an important issue which has been studied in the literatures. In this paper, we explore the task assignment problem on heterogeneous distributed system with rechargeable batteries. Our techniques to solve the problem are based on four heuristics, namely Minimum Schedule Length (MSL), Min-min Schedule Length (MmSL), Genetic Algorithm (GA), and Ant Colony Optimization (ACO). While the modifications of the MSL, MmSL and GA approaches from their original implementation are somewhat straight-forward, we design a novel structure using ACO. The performance comparisons of these four techniques are performed and the results are discussed. This paper not only gives a suggestion on which heuristic is best suited for the specific problem, but also provides a new direction to solve similar problems.

Fault tolerance is a very important aspect in critical real-time task scheduling. On multiprocessor systems, executing tasks with replication provides an additional reliability to resist potential processor failures and computing faults. For assigning real-time tasks on such systems, there must be requirements that all tasks assigned on the system meet their timing constraints, and all replicas of the same task are assigned to distinct processors. Obviously, such a reliability requirement could overload the system. In these situations, how to assign the tasks on processors to achieve the highest benefit poses a challenge. In this paper, we consider the problem of maximizing the number of successfully assigned tasks on a homogeneous distributed multiprocessor system, while satisfying the real-time constraint and system reliability requirement. Exact, greedy approximation and polynomial time approximation scheme (PTAS) algorithms are developed for the problem. Theoretical analysis, necessary proofs and experimental results that support our claims are all given.

There has been significant study of implementations of a variety of priority inversion control algorithms in uniprocessor systems, but there has been far less work done on the multiprocessor implementations of these algorithms. Herein, we will present such an evaluation of the Multiprocessor Priority Ceiling Protocol (MPCP) and the Multiprocessor Stack Resource Policy (MSRP). To our knowledge, no such empirical evaluation of these two policies has been conducted prior to this. We will show that the results differ from the previous simulation-based studies and that both policies are more or less equally effective. The main difference is the MSRPpsilas expense. We discuss the efficacy of Ada-2005 and C/POSIX. We also discuss the methods through which we have attempted to overcome Adapsilas weakness in mapping tasks to processors.

Time-critical jobs in many real-time applications have more than one feasible interval. Such jobs can be executed in any of their feasible intervals. Given a Multiple Feasible Interval (MFI) job set that is schedulable, energy can be saved by carefully selecting the executing interval for each job. In this paper, we explore the energy minimization problem for real-time systems in which jobs have multiple feasible intervals. The static and dynamic energy management schemes are both investigated to minimize the energy consumption while preserving the systempsilas feasibility. Focusing on the EDF scheduling algorithm, we first study reducing the dynamic power consumption. We show that the static optimal speed assignment problem is NP-Hard and propose a Simulated Annealing (SA) based approach to solve it. Then, we develop an online greedy algorithm to exploit the run-time slacks by ldquofetchingrdquo the eligible job from a hot spot to execute earlier, thus, reducing the dynamic energy consumption. In addition, a leakage-aware version is discussed to improve the overall energy efficiency as well. Simulation results show that all the proposed schemes can achieve significant improvements on energy efficiency while the system remains schedulable.

Programming microcontrollers is a different paradigm from microprocessor programming. The traditional way to program microcontrollers is to write the program in C or an assembly language, but modern embedded systems are more complex. The Priority-based Functional Reactive Programming (P-FRP) paradigm could make microcontroller programming better. P-FRP makes it possible to treat programs as functions (stateless) and amenable to proofs and type-safety. In this paper, we focus on the abort-and-restart event handler semantics of P-FRP, which is neither a concurrency control policy nor a true scheduling policy. Instead, it is a policy in which the most important task is scheduled first. This paper refines the response time analysis for the abort-and-restart model on single-core systems.

Embedded and real-time systems are increasingly common and complex, requiring formal specification and verification in order to guarantee their satisfaction of desirable safety and timing requirements. Real-Time Logic (RTL) has been used to capture both the specification (denoted by SP) of a real-time system and the desirable safety assertions (denoted by SA) with respect to this system specification. A verification procedure then determines whether the safety assertions hold with respect to the system specification. However, the satisfiability problem for RTL (i.e., "Can SP \rightarrow SA hold?”), as well as for other first order logics, is undecidable. Consequently, efforts have been focused on identifying nontrivial classes of formulas sufficiently practical for describing industrial real-time systems for which the verification and debugging can be done via efficient heuristics. One such class of formulas is the so-called path RTL. The first contribution of this paper is to extend the existing path RTL class without sacrificing the time complexity of the traditional path RTL heuristic for verification. This implies that we can specify and verify real-time systems, which we were unable to do using the existing path RTL, in the extended path RTL. For real-time systems with large specifications, there is a lot of room for improvement in the algorithms used for verification and debugging. The second contribution of this paper is an efficient method to perform verification and debugging of real-time systems specifications using decomposition techniques. Our idea is to decompose the constraint graph, used in existing approaches, into independent subgraphs so that it is no longer necessary to analyze the entire specification at once, but rather its individual and smaller components. However, none of the above heuristics necessarily finds an “optimal implication.” After verifying SP \rightarrow SA and deploying the system implementing SP, performance changes as a result of power saving, faulty components, and cost saving in the processing platform for the tasks specified in SP affect the computation times of the specified tasks. This leads to a different but related SP, which would violate the original SP \rightarrow SA theorem if SA remains the same. It is desirable, therefore, to determine an optimal SP with the slowest possible computation times for its tasks such that the SA is still guaranteed. This is clearly a fundamental issue in the design and implementation of highly dependable real-time/embedded systems. The third contribution of this paper tackles this fundamental issue by describing a new method for relaxing SP and tightening SA such that SP \rightarrow SA is still a theorem. We have implemented this method in the Java-based DEVO-RTL tool and tested it on several industrial real-time systems. Experimental results show that only about 10 percent of the running time of the heuristic for the verification of SP \rightarrow SA is needed to find an optimal theorem.

Optical burst switching (OBS) is a promising solution for allowing various-size data burst to be transported optically over Dense Wavelength Division Multiplexing (DWDM) without O/E/O (optical/electronic/optical) conversion. In OBS, networks, burst headers are sent ahead of the data bursts on a separate control channel to set up optical paths for the data bursts. While data bursts travel entirely in the optical domain, the burst headers have to be converted to electronic form and processed electronically. As the data channel bandwidth increases dramatically, the electronic control path for header processing is likely to become the performance bottleneck. It has been shown that control path overloading can severely degrade the performance of an OBS router. In this paper, we propose to formulate the burst header scheduling problem as an on-line time-constrained optimization problem for which we present a novel priority assignment method and a greedy on-line algorithm that consider both the urgency of the headers and the lengths of the bursts that the headers are representing. To the authors’ best knowledge, it is the first paper that targets on solving control channel’s overloading in OBS networks by improving the performance on throughput, as well as burst loss rate. Simulation results have shown that our technique is very effective.

This paper introduces the scheduling of frame-based real-time tasks in partitioning schemes for multiprocessor systems powered by rechargeable batteries. In frame-based real-time systems, a set of tasks must execute in a frame, and the whole frame is repeated. This system model is widely used in real-time communication, real-time imaging and a lot of other real-time/embedded systems. Nowadays, many of these systems are powered by rechargeable batteries. Scheduling real-time tasks on these rechargeable systems is an important yet largely ignored issue. The problem for uniprocessor systems had been studied in [1], in which an algorithm of complexity O(N) was proposed for determining the feasibility of the task set. However, it poses a challenge when doing so in a rechargeable multiprocessor system considering different characteristics of the batteries. In this paper, we first show this problem to be NP-Hard, and then propose efficient algorithms to overcome it. The simulation results have shown that our algorithms exhibit very good behaviors and they can be considered as solutions to the problem.

In this paper, we propose ANDES, a framework for detecting and finding the root causes of anomalies in operational wireless sensor networks (WSNs). The key novelty of ANDES is that it correlates information from two sources: one in the data plane as a result of regular data collection in WSNs, the other in the management plane implemented via a separate routing protocol, making it resilient to routing anomaly in the data plane. Evaluation using a 32-node sensor testbed shows that ANDES is effective in detecting fail-stop failures and most routing anomalies with negligible computing and storage overhead.

Formal specification and verification are critical to the development of safe real-time and embedded systems, which have become increasingly complex. Real-Time Logic (RTL) has been used to describe the specification and safety asser- tion of real-time systems. However, the satisfiability prob- lem for RTL, as well as other first-order logics, is unde- cidable. There exist already non-trivial fragments of RTL, like path RTL and extended path RTL, for which the veri- fication can be done efficiently. The key idea used by these RTL fragments was the so-called constraint graph. The con- straint graph can express dependencies between two events, but cannot describe dependencies between three or more events. This paper presents a larger class than existing frag- ments of RTL for which the verification problem can also be solved efficiently. Our new class is called Linear Real- Time Logic (LRTL) and includes the existing decidable RTL fragments like path RTL and extended path RTL. The LRTL class is able to express any linear timing constraint with an arbitrary number of events variables (e.g., between three or more events). The main ingredient of the LRTL class is the use of matrices instead of the constraint graph, as a more powerful data structure capable of performing the conver- sion from RTL to a propositional formula. The unsatisfi- ability of the propositional formula will ensure the safety and feasibility of the given real-time system. Experimental results show that the execution times for LRTL are better than the systems expressed in extended path RTL, and com- parable with those expressed in path RTL.

Efficient multisite job scheduling facilitates the cooperation of multi-domain massively parallel processor systems in a computing grid environment. However, co-allocation, heterogeneity, adaptability, and scalability emerge as tough challenges for the design of multisite job scheduling models and algorithms. This paper presents a new multisite job scheduling schema based on the multisite job scheduling model and the performance model for a heterogeneous grid environment. There are three key components: resource selection, reservation, and backfilling. The optimal and greedy-heuristic adaptive resource selection strategies are introduced. The conservative and easy backfilling are incorporated into the backfilling procedure. Experiments indicate that the scheduler and the algorithm are effective and perform better than a non-adaptive algorithm.

Real-time logic (RTL) is useful for the verification of a safety assertion SA with respect to the specification SP of a real-time system. Since the satisfiability problem for RTL is undecidable, there were many efforts to find proper heuristics for proving that SPrarrSA holds. However, none of such heuristics necessarily finds an "optimal implication". After verifying SPrarrSA, and the system implementing SP is deployed, performance changes as a result of power-saving, faulty components, and cost-saving in the processing platform for the tasks specified in SP affect the computation times of the specified tasks. This leads to a different but related SP, which would violate the original SPrarrSA theorem if SA remains the same. It is desirable, therefore, to determine an optimal SP with the slowest possible computation times for its tasks such that the SA is still guaranteed. This is clearly a fundamental issue in the design and implementation of highly dependable real-time/embedded systems. This paper tackles this fundamental issue by describing a new method for relaxing SP and tightening SA such that SPrarrSA is still a theorem. Experimental results show that less than 20% overhead of the running time of the algorithm for the verification of SPrarrSA is needed to find an optimal theorem

tasks in soft/firm real-time systems under overloaded conditions. In general, they are provided by application designers to guarantee the minimum levels of quality of service (QoS). Many problems concentrating in task schedulability under these constraints were investigated in the last ten years. However, little work has been done in combining the optimization of the QoS and task schedulability subject to these (m, k)-firm constraints. In this paper, we consider the problem of maximizing the guaranteed performance while maintaining a schedulable task set in periodic firm real-time systems. To quantify the performance, we propose a granularityrelated metric called Granularity of Quality of Service - Reward (GQoS-reward). We then show that maximizing the total GQoS-reward is an NP-Hard problem and a heuristic method to solve the problem is studied. In addition to the improvement to the GQoS, positive effects on other main performance metrics for soft/firm real time systems, such as effective processor utilization (EPU), total accumulated reward and instability, are also supported by the simulation results using our optimization strategy.

Embedded and real-time systems are increasingly common and complex, requiring formal specification and verification in order to guarantee their satisfaction of desirable safety and timing requirements. Real-Time Logic (RTL) has been used to capture both the specification of a real-time system and the desirable safety assertions with respect to this system specification. A verification procedure then determines whether the safety assertions hold with respect to the system specification. However, the satisfiability problem for RTL, as well as for other first-order logics, is undecidable. Consequently, efforts have been focused on identifying non-trivial classes of formulas sufficiently practical for describing industrial real-time systems for which the verification and debugging can be done via efficient heuristics. One such class of formulas is the so-called path RTL. The first contribution of this paper is to extend the existing path RTL class without sacrificing the time complexity of the traditional path RTL heuristic for verification. This implies that we can specify and verify real-time systems, which we were unable to do using the existing path RTL, in the extended path RTL. For real-time systems with large specifications, there is a lot of room for improvement in the algorithms used for verification and debugging. The second contribution of this paper is an efficient method to perform verification and debugging of real-time systems specifications using decomposition techniques. Our idea is to decompose the constraint graph, used in existing approaches, into independent subgraphs so that it is no longer necessary to analyze the entire specification at once, but rather its individual and smaller components. We have implemented this method in the Java-based DEVA-RTL tool and tested it on several industrial real-time systems.

Real-time logic (RTL) is useful for the verification of a safety assertion with respect to the specification of a realtime system. Since the satisfiability problem for RTL is undecidable, the systematic debugging of a real-time system appears impossible. A first step toward this challenge was presented. With RTL, each prepositional formula corresponds to a verification condition. The number of truth assignments of a prepositional formula can help us determine the specific constraints which should be added or modified to get the expected solutions. This paper solves an even more challenging problem specified as future work, namely, the embedding and the integration of our debugger in autonomous systems which generate real-time control plans on-the-fly, since these specifications must meet timing constraints, but without human interaction. The idea is to consider in advance all the necessary information, such as the designer's guidance. We have implemented a tool (called ADRTL) that is able to perform automatic debugging. The confidence of our approach is high as we have successfully evaluated ADRTL on several existing industrial-based applications.

Real-time logic (RTL) (F. Jahanian et al., 1986, 1987, F. Wang et al., 1994) is useful for the verification of a safety assertion with respect to the specification of a real-time system. Since the satisfiability problem for RTL is undecidable, the systematic debugging of a real-time system appears impossible. This paper provides a first step towards this challenge. With RTL, each propositional formula corresponds to a verification condition. The number of truth assignments of a propositional formula helps to determine the timing constraints which should be added or modified to the system's specification. We have implemented a tool (called SDRTL, (S. Andrei et al., 2004)) that is able to perform systematic debugging. The confidence of our approach is high as we have evaluated SDRTL on several existing industrial-based applications.

Circuit testing is the most significant cost in modern chip design and production. Due to the complexity in terms of millions of gates, manufacturers often have to truncate test patterns to make the testing feasible on ATEs with limited capacities. In this paper, we present a novel approach to this challenge by run-time coordinating the algorithm and ATE. A unique combination of a #SAT solver, checksum computation and frame testing enables the efficient incremental testing. Unlike checksums from the communication domain which can only detect the existence of stuck-at faults, our approach differentiates by also locating them. In our experimental results, our method further demonstrates a shorter testing time.

Since high-quality image/video systems based on the JPEG/MPEG compression standards often require power-expensive implementations at relatively high bit-rates, they have not been widely used in low-power wireless applications. To alleviate this problem, we designed, implemented, and evaluated a strategy that can adapt to different compression and transmission rates. (I) It gives important parts of an image higher priority over unimportant parts. Therefore, the high-priority parts can achieve high image quality, while the low-priority parts, with a slight sacrifice of quality, can achieve huge compression rate and thus save the power/energy of a low-power wireless system. (2) We also introduce a priority-driven scheduling approach into our coding algorithm, which makes the transmission of important parts earlier with more data than other parts. Through a balanced trade-off between the available time/bandwidth/power and the image quality, this adaptive strategy can satisfy users with desired images quality and lead to a significant reduction of the important parts' deadline misses.

The periodic multiframe task models and the imprecise computation techniques have been developed for scheduling real-time tasks. We introduce the imprecise computation concept into the periodic multiframe task model and derive a novel scheduling algorithm and an error compensation strategy. The paper also pays attention to the imprecise computation input error, which was often neglected in previous studies. The scheduling algorithm employs an error compensation strategy that based on the traditional largest-weight-first algorithm (LWF). The LWF algorithm guarantees that the largest weighted task executes first, thus minimizing the weighted total error in the task set. Our error compensation strategy enhances the error tolerance during the scheduling and takes maximum advantage of the processor idle time to improve the processor utilization. The experimental results show that the new task model and the new compensation strategy are practical in improving the schedulability and the processor utilization. The high error tolerance results in high schedulability and 100% processor utilization can be achieved in our algorithm. Moreover,, the scheduling algorithm is able to deal with tasks whose laxities are loose or light. Using both the error tolerance coefficient and the error compensation strategy leads to a good tradeoff between the result qualities (QoS) and the available processor time.

We examine the task of constructing bounded-time self-stabilizing rule-based systems that take their input from an external environment. Bounded response-time and self-stabilization are essential for rule-based programs that must be highly fault-tolerant and perform in a real-time environment. We present an approach for solving this problem using the OPS5 programming language as it is one of the most expressive and widely used rule-based programming languages. Bounded response-time of the program is ensured by constructing the state space graph so that the programmer can visualize the control flow of the program execution. Potential infinite firing sequences, if any, should be detected and the involved rules should be revised to ensure bounded termination. Both the input variables and internal variables are made fault-tolerant from corruption caused by transient faults via the introduction of new self-stabilizing rules in the program. Finally, the timing analysis of the self-stabilizing OPS5 program is shown in terms of the number of rule firings and the comparisons performed in the Rete network.

We examine the problem of predicting the timing behavior of knowledge-based systems for real-time applications. In particular, we describe a suite of tools which analyze OPS5 programs to understand their timing properties. First, a graphical representation of an OPS5 program is defined and evaluated. This graph represents the logical control flows of an OPS5 program. Most of our analysis is based on this data structure. Second, we describe a novel tool which verifies that an OPS5 program can terminate in finite time. If the termination of the OPS5 program is not expected, the "culprit" conditions are detected. These conditions are then used to correct the problem by adding extra rules to the original program. Third, another tool is introduced to aid timing analysis of OPS5 programs. This tool generates a set of test data which maximize the program execution time. Other functions are also provided to facilitate the timing analysis.

A rule-based system must satisfy stringent timing constraints when applied to a real-time environment. As the scale of rule-based expert systems increases, the efficiency of systems becomes a pressing concern. The most critical performance factor in the implementation of a production system is the condition-testing algorithm. We propose a new method based on the widely used RETE match algorithm. We show an approach designed to reduce the response time of rule-based expert systems by reducing the matching time. There are two steps in the method we propose: The first makes an index structure of the tokens to reduce the /spl alpha/-node-level join candidates. The second chooses the highest time tag for certain /spl beta/-nodes to reduce the amount of combinatorial match that is problematical in a real-time production system application. For this purpose, a simple compiler is implemented in C and the response time of test programs is measured.

Analyzing and reducing the execution-time upper bound of real-time rule-based expert systems is a very important task because of the stringent timing constraints imposed on this class of systems. We present a new runtime optimization to reduce the execution-time upper bound of real-time rule-based expert systems. In order to determine rules to be evaluated at runtime, a predicate dependency list, which consists of a predicate, its active rule set and corresponding inactive rule set, is created for each predicate in a real-time rule-based program. Based on the predicate dependency list and the current value of each variable, the new runtime optimization dynamically selects rules to be evaluated at runtime. For the timing analysis of the proposed algorithm, we introduce a predicate-based rule dependency graph, a predicate-based enable-rule graph, and their construction algorithm. We also discuss the bounded time of the equational logic rule-based program using the predicate-based rule dependency graph as well as the predicate-based enable-rule graph. The implementation and performance evaluation of the proposed algorithm using both synthetic and practical real-time rule-base programs are also presented. The performance evaluation shows that the runtime optimizer reduces the number of rule evaluations and predicate evaluations as well as the response time upper bound significantly, and the new algorithm yields better execution-time upper bound compared to other optimization methods.

Existing match algorithms treat the matching process like the querying process of relational databases. Owing to the combinatorial nature of the matching process, the match time greatly varies in different recognize-act cycles. Current match algorithms utilize local matching support networks with redundant working memory elements shared among rules involving the same classes. Since the match time is a dominant factor in the total execution time of a production system, such large match time makes production systems with existing match algorithms unsuitable for many applications. To reduce match time, we introduce the Heuristically-Annotated-Linkage (HAL) match algorithm. HAL differs from traditional match algorithms in that HAL employs a fixed-traversal-distance pseudobipartite network approach of treating rules and classes as objects, or nodes, in only one global pseudobipartite-graph-like connection and communication scheme. In addition, HAL is more efficient than other existing match algorithms because it is capable of immediate characterization of any new datum upon arrival. This paper reviews existing match algorithms, presents HAL, and analyzes the performance of HAL in comparison with existing algorithms.

A rule-based system must satisfy stringent timing constraints when applied to a real-time environment. The most critical performance factor in the implementation of a production system is the condition-testing algorithm. We show an approach designed to reduce the response time of rule-based expert systems by reducing the matching time based on RETE. There are two steps in the method we propose: the first makes an index structure of the tokens to reduce the /spl alpha/-node-level join candidates; the second chooses the highest time tag for certain /spl beta/-nodes to reduce the size of the /spl beta/-memory and to keep the strategy of the RETE network. These steps reduce the amount of combinatorial match that is problematical in a real-time production system application.

This paper examines the task of constructing bounded-time self-stabilizing rule-based systems that take their input from an external environment. Bounded response-time and self-stabilization are essential for rule-based programs that must be highly fault-tolerant and perform in a real-time environment. We present an approach for solving this problem using the OPS5 programming language as it is one of the most expressive and widely used rule-based programming languages. Bounded response-time of the program is ensured by constructing the state space graph so that the programmer can visualize the control flow of the program execution, and any possible infinite execution leaps should be detected. Both the input variables and internal variables are made fault tolerant from corruption caused by transient faults via the introduction of new self-stabilizing rules in the program. Finally the timing analysis of the self-stabilizing OPS5 program is shown in terms of the number of rule firings and the comparisons performed in the Rete network.

Future computer networks are expected to carry bursty real-time traffic with stringent time-delay requirements. Popular shortest-path routing protocols have the disadvantage of causing bottlenecks due to their single-path routing. We propose a real-time routing and scheduling scheme that randomly distributes the traffic load over all available paths to the destination for load balancing and transmits the packet with the most urgency ahead of the other packets at a switch in a packet-switched network with two objectives-minimizing packet loss in the network and maximizing network throughput. Our scheme consists of two components, a routing algorithm and a scheduling algorithm. The routing algorithm randomly distributes data packets over the whole network to remove bottlenecks caused by the single-path routing of shortest-path routing protocols. The end-to-end delay is bounded by the scheduler, which uses a least-laxity scheduling algorithm. Our simulation results indicate that the proposed scheme decreases the number of packets dropped due to deadline miss and due to buffer overflow in transit in a network and increases network throughput. A desirable by-product is that the traffic load on the network tends to get evenly distributed.

A high-priority real-time connection is denied admission to an ATM network if insufficient bandwidth is available along all suitable paths through the network. Bandwidth reallocation and dynamic active channel rerouting are techniques that allow a node to select lower-priority channels and reallocate their bandwidth to the new higher-priority connection being admitted. The selected lower-priority channels must then be rerouted through the network so that their QoS requirements can still be satisfied. A local detouring technique, using backup channels, is employed so that reroutes can be handled quickly and efficiently, without violating the QoS requirements of the rerouted channels. Techniques are described which ensure that transmitted data is received on time and in sequence, which is essential for real-time communications. The SANRoP (Simulator for ATM Network Routing Protocols) cell-level discrete event simulator was developed to simulate these protocols in an ATM network in order to determine how well they perform.

The paper focuses on the problem of determining a priori the maximal response time of rule based programs. The response time analysis problem is an important problem, especially for real time systems. We study this problem in the context of OPS5 production systems. Two aspects of the response time of a program are investigated, the maximal number of rule firings and the maximal number of basic comparisons made by the Rete network during the execution of the program. The response time analysis problem is in general undecidable. However, a program terminates in a finite time if the rule triggering pattern of this program satisfies certain conditions. We present four such termination conditions for OPS5 production systems. An algorithm for computing an upper bound on the number of rule firings is then given. To have a better idea of the time required during execution, we present an algorithm that computes the maximal time required during the match phase in terms of the number of comparisons made by the Rete network. This measurement is sufficient since the match phase consumes about 90 percent of the execution time.

Embedded rule-based expert systems must satisfy stringent timing constraints when applied to real-time environments. The paper describes a novel approach to reduce the response time of rule-based expert systems. The optimization method is based on a construction of the reduced cycle-free finite state space graph. In contrast with traditional state space graph derivation, the optimization algorithm starts from the final states (fixed points) and gradually expands the state space graph until all of the states with a reachable fixed point are found. The new and optimized system is then synthesized from the constructed state space graph. The authors present several algorithms implementing the optimization method. They vary in complexity as well as in the usage of concurrency and state-equivalency-both targeted toward minimizing the size of the optimized state space graph. Though depending on the algorithm used, optimized rule-based systems: (1) in general have better response time in that they require fewer rule firings to reach the fixed point; (2) are stable, i.e., have no cycles that would result in the instability of execution; and (3) have no redundant rules. They also address the issue of deterministic execution and propose optimization algorithms that generate the rule-bases with single corresponding fixed points for every initial state. The synthesis method also determines the tight response time bound of the new system and can identify unstable states in the original rule-base.

Article Reducing match time variance in production systems with HAL Share on Authors: Pou-yung Lee Real-Time Systems Laboratory, Department of Computer Science, University of Houston - University Park, Houston, Texas Real-Time Systems Laboratory, Department of Computer Science, University of Houston - University Park, Houston, TexasView Profile , Albert Mo Kim Cheng Real-Time Systems Laboratory, Department of Computer Science, University of Houston - University Park, Houston, Texas Real-Time Systems Laboratory, Department of Computer Science, University of Houston - University Park, Houston, TexasView Profile Authors Info & Claims CIKM '97: Proceedings of the sixth international conference on Information and knowledge managementJanuary 1997 Pages 309–316https://doi.org/10.1145/266714.266916Online:01 January 1997Publication History 2citation211DownloadsMetricsTotal Citations2Total Downloads211Last 12 Months2Last 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

One major requirement for multimedia systems is the efficient transmission of multimedia information over a communication or computer network. Several commercial products heave been developed to apply compression techniques to images and videos in order to reduce their transmission time. Sufficient available time and bandwidth lead to satisfactory results, but image/video loss occurs if these resources are insufficient. Using imprecise computation theory, we can achieve a good tradeoff between the quality of the transmitted image/video and the available resources such as the time for transmission. However, for a compressed image file, this very flexible technique cannot be easily applied since a compressed file cannot be uncompressed if it is not transmitted completely. This paper proposes an imprecise compressed image/video transmission technique which combines the advantages of both compression and imprecise computation for the first time. Our experimental results show that the proposed algorithm has better results compared to simply using compression or imprecise transmission techniques, and has a good potential for commercial use.

The paper presents an approach to pre-process and post-process TIFF image files in real-time applications for maintaining an acceptable image quality when these files are transmitted in a congested ATM network. Compared to existing techniques, the approach introduces a very low transmission and computational overhead, allows a higher cell-loss rate, and produces a less image degradation. In this approach, the preprocessor rearranges the content of image files, and then packs these fixed image files into ATM cells for transmission. The post-processor unpacks the cells, restores the original content orders, and if part of the data has been discarded, performs data recovery to reconstruct imprecise image files as close to their original versions as possible. By marking an appropriate number of cells, a user can specify an acceptable lower bound on the quality of the image that is delivered at the destination. This mates it possible to control and know which part of the image data can be discarded. The experimental results show that by using the proposed approach, the quality of the received/recovered images decreases more slowly than the proportional increase in network congestion.

Complexity metrics, such as McCabe's cyclomatic number of a program control graph and Halstead's number of operator/operand occurrences have been used extensively to measure the structural complexity of procedural programs. However, few suitable complexity metrics have been developed for rule-based programs written in OPS5 and OPS5-like rule-based languages. With the increasingly common use of rule-based languages in knowledge-based systems, this paper describes new complexity metrics to more accurately measure the complexity of OPS5 rule-based programs. The practicality of these metrics is empirically demonstrated by applying them to measure the complexity of a suite of benchmark: OPS5 expert systems.

Real-time rule-based expert systems are embedded decision systems that must respond to changes in the environments within stringent timing constraints. Given a program p, the response time analysis problem is to determine the response time of p. This problem consists of: determining whether or not the execution of p always terminates in bounded time; and computing the maximal execution time of p. The Equational Logic (EQL) language is a simple language designed for real-time applications. It has been proved by A.K. Mok (1989) that the response time analysis problem is undecidable if the program variables have infinite domains, and is PSPACE-hard in the case where all of the variables have finite domains. However, we have observed that the use of a simple syntactic and semantic check on programs coupled with other techniques such as state space graph checks can dramatically reduce the time needed in the analysis. There are sets of syntactic and semantic constraint assertions such that if the set S of rules satisfies any of them, then the execution of S always terminates in bounded time. Each of these sets of syntactic and semantic constraint assertions is called a Special Form. The focus of the paper is on proving the existence of two Special Forms and determining tight response time upper bounds of EQL rule-based programs. For each known Special Form, an algorithm used to calculate the maximal response time of programs satisfying this Special Form is presented. Additionally, to enhance the applicability of the proposed algorithms, we show how the General Analysis Algorithm can be used with these algorithms.>

Real-time expert systems are embedded decision systems which must respond to changes in the environments within stringent timing constraints. A major problem impeding the use of rule-based expert systems in real-time environments is the difficulty in predicting the response time of these rule-based systems. In this paper, we tackle this problem with a fast, partially parallelizable response time analysis algorithm for a class of EQL rule-based programs with constant assignments in the action parts of the rules.

Real-time expert systems are embedded decision systems which must respond to changes in the environments within stringent timing constraints. Given a program p, the response time analysis problem is to determine the maximal response time of p. In this paper, we tackle this problem with a response time upper bound algorithm for a class of EQL rule-based programs whose variables range over finite domains, This algorithm computes a response tame upper bound of the given program by determining the maximal number of rule firings which result from the firings of individual rules enabled at the invocation.>

Rule-based expert systems are increasingly used to monitor and control the operations of complex real-time systems which require intensive knowledge-decision processing and human expertise. These embedded AI systems must respond to events in the rapidly changing external environment so that the results of the expert system's computation in each monitor-respond cycle are valid in safely operating the real-time system. Determining how fast an expert system can respond under all possible situations is a difficult problem. We have developed an efficient analysis methodology for a large class of rule-based EQL programs to determine whether a program in this class has bounded response time. In particular, we have identified several sets of primitive behavioral constraint assertions: an EQL program which satisfies all constraints in one of these sets of assertions is guaranteed to have bounded response time. Here, we enhance the applicability of our analysis technique by introducing a facility with which the rule-based programmer can specify application-specific knowledge that is too difficult to be mechanically detected in the new language Estella in order to determine the performance of an even wider range of programs. We also describe efficient algorithms for implementing the analysis tools.>

The problem of automated recovery in distributed real-time rule-based systems where internal variables may be corrupted during computation as a result of transient faults is discussed. Given a distributed rule-based program p with bounded response time, the problem is to derive a self-stabilizing program q that implements p with the constraint that q must also have bounded response time. An approach for solving this problem for a class of rule-based programs with bounded response time is presented.>

The Estella general analysis tool (E-GAT) is a computer-aided software engineering tool for performing response time analysis of real-time production systems written in the EQL rule-based language. E-GAT detects potential timing errors statically, making it a powerful aid for the rapid prototyping and development of expert systems with guaranteed response time. It is based on a powerful analysis methodology which exploits the identification of rule sets satisfying certain general behavior constraint assertions. A description is presented of the implementation of E-GAT with efficient algorithms.>

The response time analysis of rule-based expert systems is discussed. The rule-based production system MRL (macro-rule-based language) is introduced. MRL has been designed to facilitate more accurate analysis of the response times of programs while maintaining the flexibility and expressiveness of traditional production systems such as OPS5. Research on modular analysis of rule-based systems is described. Several timing analysis algorithms based on this approach have been developed. One of them, a fixed-point detection algorithm is discussed to show that efficient and effective analysis of MRL programs can be achieved. In particular, a general technique called the transfer principle is introduced for exploiting analysis algorithms which are simpler to analyze. The design of the match algorithm Rhyme, an algorithm uniquely suited for more accurate analysis of the performance of real-time expert systems, is presented.>