End-to-end delay is one of the most important timing constraints in distributed real-time systems (DRTS) [1], especially in the area of wireless sensor network (WSN) or Internet of Things (IoT). Since we may need to collect data from sensor nodes and react immediately. Thus, tasks must be executed in a distance-constrained manner. That is, the temporal distance between any two consecutive executions of a task should always be less than a certain amount of time. In DRTS, transactions are decomposed into a group of tasks, and periodic model might not be efficient enough, since the temporal distance between two consecutive executions of task could be two times of its period in the worst case. Moreover, an execution will not be always ready in a period, which might incur extra end-to-end delay in DRTS. Pinwheel scheduling algorithms have been designed to schedule tasks with distance constraint. But meeting distance constraints in a node does not guarantee minimized end-to-end delay of a transaction. Therefore, DSr, a distributed pinwheel scheduling algorithm, focuses on reducing end-to-end delay systematically and synchronously [2]. Although the pinwheel scheduling algorithms provide simple scheduling bounds and approaches for fully utilized tasks, for the simpler sensor nodes with limited hardware timer support, it might not be easy to execute the pinwheel scheduling algorithms accordingly and guarantee the synchronous results. We find that there exists a simple feasible algorithm (e.g. First In First Out, FIFO) with tight scheduling bound. Although it is always schedulable only in low-utilized systems using FIFO, it results in shorter endto- end delays than DSr in most cases with high utilization. To simplify, we focus only on the system of two nodes with the same utilization. As shown in Figure 1, we simulate the total end-to-end delay with different number of transactions, n, and utilization, ρ, and find that FIFO outperforms DSr. That means transactions can be finished earlier using FIFO. Furthermore, we also find that the relative length of execution time effects the schedulability. As shown in Figure 2, where r stands for the largest ratio of length of execution times, the smaller r, the closer length of execution times, or the lower ρ, as in WSN, outperforms. Therefore, we believe FIFO has large potential in DRTS, especially in low-utilized DRTS, which commonly presents the case of WSN [3] or IoT.

Virtualization has been a well-studied topic for traditional servers. As the demand for the support of virtualization on mobile devices emerged, it again became a popular research topic. However, most research work focused on the applications of mobile virtualization. Detailed knowledge of the characteristics of mobile devices is still lacking. In this paper, we focus on the memory management of mobile virtualization, and propose an optimized page translation oPT with hardware/software co-design. The usage pattern of mobile devices is also considered in the design so it is optimal in terms of the hit ratio of the second stage. The variability of translation time in the second stage is eliminated to provide nearly the same behavior as the non-virtualized architecture. We verify the correctness and feasibility of oPT with a formal proof and a comprehensive evaluation based on both software emulation and hardware implementation. The results indicate oPT can outperform the most popular method. The number of memory accesses is reduced by 51.38 to 56.01 percent, and the average translation time is reduced by 78.63 percent. In addition, the power consumption of the hardware unit in oPT is only about one third that of the traditional method.

The household structure is an important aspect of population based simulation. How to generate a mock population with specific household structure characteristics is thus an important question. The network structure is one of the dominant factors for contact-based disease transmission. And household structure is the most important source of close contact among small groups. We identify the percentage of elderly-children households as an important character and study the process to generate mock population with specified percentage of elderly-children households. The generated mock populations are fed into the agent-based simulation module to study the impact of household structure on vaccination policy.

As the number of IPs in a multimedia Multi-Processor System-on-Chip (MPSoC) continues to increase, concurrent memory accesses from different IPs increasingly stress memory systems, which presents both opportunities and challenges for future MPSoC design. The impact of such requirements on the system-level design for MPSoC is twofold. First, contention among IPs prolongs memory access time, which exacerbates the persisting memory wall problem. Second, longer memory accesses lead to longer IP stall time, which results in unnecessary leakage waste. In this article, we propose two memory access-aware system-level design approaches for performance and leakage optimization. To alleviate the memory wall problem, we propose a Hierarchical Memory Scheduling (HMS) policy that schedules memory requests from the same IP and application consecutively to reduce interference among memory accesses from different IPs with a fairness guarantee. To reduce IP leakage waste due to long memory access, we propose a memory access-aware power-gating policy. A straightforward power-gating approach is to power gate an IP when it needs to fetch data from memory. However, due to the response time variation among memory accesses, aggressively power gating an IP whenever a memory request occurs may result in incorrect power-gating decisions. The proposed memory access-aware power-gating policy makes these decisions judiciously, based on the predicted memory latency of an individual IP and its energy breakeven time. The experimental results show that the proposed HMS memory scheduling policy improves system throughput by 42% compared to First-Come-First-Serve (FCFS) and by 21% compared to First-Ready First-Come-First-Serve (FR-FCFS) on an MPSoC for mobile phones. For the improvement of fairness, HMS improves fairness by 1.52× compared to FCFS and by 1.23× compared to FRFCFS. In the aspect of leakage optimization, our memory access-aware power-gating mechanism improves energy savings by 3.88× and reduces the performance penalty by 70% compared to conventional timeout-based power gating. We further demonstrate that our HMS memory scheduler can regulate memory access orders, thereby reducing memory response time variation. This leads to more accurate power-down decisions for both conventional timeout power gating and the proposed memory access- aware power gating.

Recently, the significant progress in embedded microprocessors made it practical to support virtualization on mobile devices. Unfortunately, memory management has not been well studied in consideration of the characteristics of mobile virtualization due to the challenging aspects on both hardware and software. With a formal proof on a novel design of page translation at the second stage, we propose a novel design of page translation on both hardware and software with higher translation speed, lower variance of latency, and lower hardware complexity. The experimental results suggest it can reduce memory access by 51.37% to 56.01% as compared with the traditional approach.

With the rapid increase of multimedia technology [1], [2], the support of network traffic has become an important issue. Thus many protocols have been developed to address this issue in different network layers such as Real Time Streaming Protocol (RTSP) [3], Smooth Streaming [4] in application layer, and Real time Protocol (RTP) in transport layer. The common characteristic of these protocols is the requirement of data smoothing to support modern application like intelligent home and vehicular network. In addition, smart phone and wireless sensor network(WSN) [5] do not support all protocols, indeed, they may only support Transmission Control Protocol(TCP) or User Data gram Protocol(UDP). This implies that the network bandwidth will nor be good enough to play high quality multimedia streaming and support complicated network structure. In this paper, we present a smooth data streaming approach on application layer to reduce packet retransmission and improve performance. The proposed approach can provide smooth data streaming and reduce response time with the aid of data caching or data compression without increase the complexity of network protocol. In order to decrease the development complexity arising from UDP, instead, we implement the proposed approach based on TCP. We also analyze the impact of this work and discuss challenges in TCP in this paper. The result shows that the proposed approach can stabilize smooth data transmission and improve performance by 20% to 35% for benchmarks.

As the Web 2.0 technology is becoming popular, people are eager to access the Internet at anytime and anyplace. In this paper, we present an Internet connectivity sharing system, called iShare, based on the concept of ad-hoc networking. In iShare, the efficiency and load-balancing issues are considered. Also, the functionalities of gateway discovery/selection and routing inter-operability as well as address assignment, IP tunneling, and firewall/NAT are designed and implemented. The experimental results for our implementation prototype indicate that the performance of our iShare system is acceptable for Internet connectivity to access HTTP services.

Virtualization has been widely adopted on servers for various purposes such as server consolidation, cloud computing, and so on. Recent years, the trend spreads on embedded systems, although it once seemed to be an impractical idea because of the limited capability of embedded processors. To further lower the overhead of adopting virtualization on embedded systems, we design an optimization technique, called inline emulation, to reduce the cost spending on paravirtualizing operating systems. Inline emulation can also be used in various virtualization environments to increase the performance of emulating privileged instructions. We implement inline emulation for ARMv5 architecture and evaluate in Android Emulator. The result shows it runs much faster, up to 7.4 times, than the common Para virtualization technique for cache-related operations and suggests that it not only lowers the development cost but also increases system responsiveness.

Pipelining has been applied in many area to improve performance by overlapping executions of computing stages. However, it is difficult to apply on H.264/AVC decoding in frame level, because the bitstreams are encoded with lots of dependencies and little parallelism is left to be explored. Even slice-level parallelism in H.264 is intuitive, because there is usually only one slice in a frame, it is not very applicable. Therefore, after some software improvement, many researches can only adopt hardware assistance. Fortunately, pure software pipelining can be applied on H.264/AVC decoding in macroblock level with reasonable performance gain.

In multicore environment, using multiple threads is a common useful approach to improve application performance. Nevertheless, even in many simple applications, the performance might degrade when the number of threads increases. Users usually impute this phenomenon to the overhead of creation or termination of threads. However, in our observation, the more significant effect is the dispatching of threads. We discuss the problems on using threads, and present a novel user dispatching mechanism (UDispatch) that provides controllability in user space to improve application performance. Since user threads cannot directly control system resources, a virtual device is adopted between user space and operating system for portability and efficiency instead of adding new system calls through kernel modification. We also experiment UDispatch through multithreading multimedia applications. The results show that a skipline application speeds up to 111.3% and 111.6% on a 4-core machine and an 8-core machine, respectively, and an optimized H.264/AVC decoder speeds up to 18.4% on a 4-core machine.

For an embedded processor, the cache design almost occupies half chip area and power consumption. According to Amdahl's law, if the power consumption of cache memories is reduced, the embedded processor can significantly save much power. However, the cache misses result in the penalty of thousands of cycles waiting and power consumption due to increasing the number of external memory access. Based on the above reason, the phased cache design is proposed and can largely improve the power consumption which wastes a set-associative cache. In this paper, the embedded pipelining processor without stalling and low-power phase cache is practiced with high-level simulation to achieve high-performance and low-power design. As experimental results, the proposed phase cache can reduce 44% power consumption compared with traditional one-access-cycle cache and eliminate pipeline stalls incurred by phased cache with only 6% gate count overhead.

In hard-real-time environment, scheduling periodic tasks upon multiprocessors is one of the most popular problems where uniform multiprocessor scheduling is a well-known one. In this platform, execution time of each task in one processor is proportional to the computing capacity of this processor. From previous works, we know there are only approximate feasible solutions for on-line scheduling on uniform multiprocessors. In this paper, with task migration, we first present a novel model called T-Ler plane to describe the behavior of tasks and processors, and two optimal on-line algorithms based on T-Ler plane to schedule real-time tasks with dynamic-priority assignment on uniform multiprocessors. To make it practical and to reduce context switches, we also present a polynomial-time algorithm to bound the times of rescheduling in a T-Ler plane. Since task migration is easier in SOC multicore processors, our result might be applicable and adapted to many asymmetric multicore platforms.

As the increasing of system performance and computing power, embedded systems are more complicated and interactive. Therefore, operating system (OS) plays a more important role in embedded systems to utilize various hardware and software resources. However, no OS can meet all requirements of various embedded systems. Due to the advance of reconfigurable processors, system requirements can be more dynamic. Embedded OS has becoming more critical in the development of embedded systems and thus there is a strong need of configurable embedded OS to better and faster build up the target system. In this paper, we propose a configurable OS, called COS, based on SOA (service-oriented architecture) for embedded SoC (system on a chip) systems to build an application specific OS according to the system requirements. COS can be easily configured to better utilize the resources of the target embedded platform and have better support to the embedded application. Moreover, the COS can easily extend new features or functionalities of other OSes and even be adapted to the designs of other OSes. We implement COS on an ARM platform to prove its configurability and also evaluate its overhead. We believe that COS can be configured to meet the various requirements in embedded SoC systems and help to speed up the embedded system development process

For the success of an SoC design, a design platform and some key design technologies are needed. For this purpose, a research project in "Technology Development Program for Academia" was granted recently in Taiwan to develop the following technologies toward a high-performance low-power SoC design platform. First, a soft intellectual property (soft IP) and related RTOS, compiler, and integrated design environment (IDE) software of an Advanced Taiwan VLTW DSP Processor Core, which can be used as the Star IP of an SoC design platform, will be developed. Second, low-power and low-voltage digital and mixed-signal circuit design technologies will be developed based on the advanced MTCMOS process. Third, some key multimedia and communication soft or hard IPs will be developed. The developed advanced key technologies can be used as the technology driver to facilitate the design of SoC-based products, and they will also help to enhance the design capability of the Taiwan SoC industry. In this paper, we introduce the research project and focus on architecture and software technologies developing in one of the subitems.

Energy consumption is a critical design issue in embedded systems, especially in battery-operated systems. Maintaining high performance while extending the battery life is an interesting challenge for system designers. Dynamic voltage scaling and dynamic frequency scaling allow us to adjust supply voltage and processor frequency to adapt to the workload demand for better energy management. Because of the high complexity involved, most solutions depend on heuristics for online power-aware real-time scheduling or offline time-consuming scheduling. In this paper, we discuss how we can apply pinwheel model to power-aware real-time scheduling so that task information, including start times, finish times, preemption times, etc, can be efficiently derived using pinwheel model. System predictability is thus increased and under better control on power-awareness. However, job execution time may be only a small portion of its worst case execution time and can only be determined at runtime. We implement a profiling tool to insert codes for collecting runtime information of real-time tasks. Worst case execution time is updated online for scheduler to perform better rescheduling according to actual execution. Simulations have shown that at most 50% energy can be saved by the proposed scheduling algorithm. Moreover, at most additional 33% energy can be saved when the profiling technique is applied.

Summary form only given. While excellent research results have been proposed for query optimization, little work has been done for the scheduling of query execution plans. We target the optimization problem of the schedule lengths of query execution plans in a symmetric multiprocessor (SMP) database system. We show the NP-hardness of the optimization problem. A critical-path-based algorithm is proposed to minimize the schedule length of a collection of query execution plans. When each query execution plan has a tree or a directed acyclic graph structure, we show that the approximation ratios of our proposed algorithm are 2 and (3 - 2/M), respectively, where M is the number of processors in the system. When the proposed algorithm is adopted for online usages, the competitive ratio of the algorithm is proven being (3 $2/M). The proposed algorithm is optimal when there is a sufficient number of processors. The performance of the proposed algorithm is evaluated based on the TPC-C benchmark.

Processes running in a multiple-disk environment may share non-preemptible resources on the processor and, at the same time, request services from disk subsystems. In this paper, we propose a methodology which is efficient and easy to implement for scheduling processes in multiple-disk environments. In other words, our methodology addresses the scheduling of real-time processes which may stop to wait for disk I/O without releasing any locked semaphores. Our proposed methodology is a variation of the well-known priority ceiling protocol to schedule processes running in multiple-disk environments. The capability of the proposed methodology is verified by a series of simulation experiments under different workloads of CPU-bound and I/O-bound processes in multiple-disk environments, for which we have some encouraging experimental results.

Real-time distributed applications have timing constraints on tasks running on several processors. To design real-time systems with end-to-end performance requirements, we need to have algorithms to schedule and to coordinate tasks on different processor nodes. An end-to-end scheduling approach based on the pinwheel scheduling model is presented for distributed real-time systems, We show how tasks on different nodes may be transformed to have periods consisting of only harmonic numbers. With harmonic periods, we can use a polynomial-time algorithm to find the start and finish times of each task on each node. Phase alignment algorithms are then applied to adjust the phases between schedules of neighboring nodes so that the overall end-to-end delay is minimized. Using the distributed pinwheel model, schedules on different nodes are synchronized to lessen the delays. For many real-time systems, this approach provides a predictable performance and a short end-to-end delay.

Pinwheel scheduling algorithms can be used to produce distance-constrained real-time system schedules where the temporal distance between any two consecutive completions of a task must be less than a pre-defined time interval. A pinwheel schedule can be generated off-line and executed cyclically. Such an approach provides a good predictability and allows for off-line schedule optimization. However, the static approach is inflexible and may require a large space to store the schedule. By taking advantage of the harmonic property between pinwheel task periods, one can generate the pinwheel schedule dynamically at run time in polynomial time and space. In this way, efficient and flexible time-driven schedulers can be implemented. The authors show the algorithms and study the practical issues on implementing on-line pinwheel schedulers.

Several pinwheel schedulers have been reported previously for scheduling real-time systems in which the temporal distances between consecutive executions of tasks must be less than their respective distance constraints. The scheduler Sr has been used for task sets with real number distance constraints and execution times. Sr transforms the distance constraints in a system into harmonic values with a base of 2. The authors present a pinwheel scheduler Sr/sup b/ which is derived from Sr using any base greater than or equal to d. The schedulability condition of Sr/sup b/ is presented and its optimality is proved. They also study the performance of Sr/sup b/ by simulation and compare it with a near-optimal heuristic algorithm HSr.

Algorithms for allocating resources and scheduling tasks are important to the success of many real-time systems with end-to-end performance requirements. In this paper, an end-to-end scheduling model based on the pinwheel scheduling algorithms is presented for distributed real-time systems. We discuss how tasks on different nodes may be transformed to have harmonic periods. We also present algorithms to adjust the phases between schedules on neighboring nodes so that the overall end-to-end delay is reduced. Using the pinwheel approach, schedules on different nodes are closely synchronized and more static. However, for many real-time systems, this practical approach may provide a more predictable performance and a shorter end-to-end delay.