LSM-Tree is a critical data structure designed for write-optimized, user-facing key-value databases. However, LSM-Trees must frequently perform data merge operations to maintain read efficiency and discard obsolete data. These operations generate a considerable amount of write activity on the storage device (e.g., an SSD), which can drastically reduce the device’s lifespan. Often, these merges involve rewriting data that has not changed, a process that could be avoided. Recognizing this, we introduce “Bloom Merge,” an innovative merge strategy for LSM-Trees specifically developed for SSD. Based on the key distribution in LSM-Tree’s SSTables, this method selectively and efficiently perform merges, only when necessary. It also mitigates the potential negative impact on read performance through the strategic use of in-memory Bloom Filters. We present several key insights into determining the optimal conditions for merging and outline strategies that achieve a balanced improvement in both read and write performance. Our evaluation demonstrates that Bloom Merge significantly enhances write efficiency while reducing unnecessary operations.

With the proliferation of sensors and the emergence of novel applications, IoT data has grown exponentially in recent years. Given this trend, efficient data management is crucial for a system to easily access vast amounts of information. For decades, B + -tree-based indexing schemes have been widely adopted for providing effective search in IoT systems. However, in systems with pre-distributed sensors, B + -tree-based indexes fail to optimally utilize the known IoT data distribution, leading to significant write overhead and energy consumption. Furthermore, as non-volatile memory (NVM) technology emerges as the alternative storage medium, the inherent write asymmetry of NVM leads to instability issues in IoT systems, especially for write-intensive applications. In this research, by considering the write overheads of tree-based indexing schemes and key-range distribution assumption, we rethink the design of the tree-based indexing schemes and propose an adaptive pre-built tree (APB-tree) indexing scheme to reduce the write overhead in serving insertion and deletion of keys in the NVM-based IoT system. The APB-tree profiles the hot region of the key distribution from the known key range to pre-allocate the index structure that alleviates online index management costs and runtime index overhead. Meanwhile, the APB-tree maintains the scalability of a tree-based index structure to accommodate the large amount of new data brought by the additional nodes to the IoT system. Extensive experiments demonstrate that our solution achieves significant performance improvements in write operations while maintaining effective energy consumption in the NVM-based IoT system. We compare the energy and time required for basic key operations such as Put(), Get(), and Delete() in APB-trees and B + -tree-based indexing schemes. Under workloads with varying ratios of these operations, the proposed design effectively reduces execution time by 47% to 72% and energy consumption by 11% to 72% compared to B + -tree-based indexing schemes.

For many emerging data-centric computing applications, it is a key capability to efficiently store, manage, and access multidimensional data. To achieve this, many multidimensional index data structures have been proposed. However, when existing multidimensional index data structures are maintained on modern nonvolatile memories (NVMs), such as NAND flash memory, they often face challenges in effective management of multidimensional data and handling of memory medium peculiarities, such as the write-once property and the need for block reclamation of NAND flash memory. Without appropriate management, these challenges often result in serious amplification of the read/write traffic, which degrades the performance of multidimensional data structures. Motivated by the urgent needs of efficient multidimensional index data structures on modern NVMs, we propose the FIRM-tree, a time-efficient and space-economic index data structure for multidimensional point data on NAND flash memory. Unique to the prior work, the FIRM-tree holistically utilizes RAM and flash memory space, and dedicatedly leverages the page reprogrammability of modern NAND flash memory, to enhance data access performance and flash management overheads. We then verify our proposal through analytical and experimental studies, where the results are quite encouraging.

Skyrmion racetrack memory (SK-RM) has demonstrated great potential as a high-density and low-cost nonvolatile memory. Nevertheless, even though random data accesses are supported on SK-RM, data accesses can not be carried out on individual data bit directly. Instead, special skyrmion manipulations, such as injecting and shifting, are required to support random information update and deletion. With such special manipulations, the latency and energy consumption of skyrmion manipulations could quickly accumulate and induce additional overhead on the data read/write path of SK-RM. Meanwhile, injection operation consumes more energy and has higher latency than any other manipulations. Although prior arts have tried to alleviate the overhead of skyrmion manipulations, the possibility of minimizing injections through buffering skyrmions for future reuse and energy conservation receives much less attention. Such observation motivates us to propose the concept of skyrmion vault to effectively utilize the skyrmion buffer track structure for energy conservation through maximizing the lifespan of injected skyrmions and minimizing the number of skyrmion injections. Experimental results have shown promising improvements in both energy consumption and skyrmions' lifespan.

Even though flash memory is widely used in many applications as storage due to its high performance, demands for lower storage cost and better I/O performance are still high because of the continuous growth of data. Data deduplication has the potential to address these issues by eliminating redundant writes in I/O workloads and different strategies have been proposed to improve its efficiency. However, existing designs mainly rely on time-consuming SHA-1 fingerprint scheme or byte-by-byte comparison to identify duplicate data, and these methods cause much overhead and become a bottleneck in data deduplication. To tackle this issue, we propose the hierarchical fingerprint scheme (HF-Dedupe) to improve the efficiency of data deduplication for flash-based storage systems. By leveraging multiple levels of light-weight hashes in the fingerprint, our design only takes the minimal effort to distinguish different data in write traffic. In order to evaluate our design, a series of experiments were conducted based on trace-driven simulations. Compared with other designs, the experimental results show that HF-Dedupe further reduces the deduplication time by 34.76%-65.02 % while retaining high deduplication ratio, and therefore achieves the most improvement to overall I/O performance.

In the year passed, rarely a month passes without a ransomware incident being published in a newspaper or social media. In addition to the rise in the frequency of ransomware attacks, emerging attacks are very effective as they utilize sophisticated techniques to bypass existing organizational security perimeter. To tackle this issue, this paper presents “DeepWare,” which is a ransomware detection model inspired by deep learning and hardware performance counter (HPC). Different from previous works aiming to check all HPC results returned from a single timing for every running process, DeepWare carries out a simple yet effective concept of “imaging hardware performance counters with deep learning to detect ransomware,” so as to identify ransomware efficiently and effectively. To be more specific, DeepWare monitors the system-wide change in the distribution of HPC data. By imaging the HPC values and restructuring the conventional CNN model, DeepWare can address HPC’s nondeterminism issue by extracting the event-specific and event-wise behavioral features, which allows it to distinguish the ransomware activity from the benign one effectively. The experiment results across ransomware families show that the proposed DeepWare is effective at detecting different classes of ransomware with the 98.6% recall score, which is 84.41%, 60.93%, and 21% improvement overRATAFIA,OC-SVM, andEGBmodels respectively. DeepWare achieves an average MCC score of 96.8% and nearly zero false-positive rates by using just a 100 ms snapshot of HPC data. This timeliness of DeepWare is critical on the ground that organizations and individuals have the opportunity to take countermeasures in the first stage of the attack. Besides, the experiment conducted on unseen ransomware families such as CoronaVirus, Ryuk, and Dharma demonstrates that DeepWare has excellent potential to be a useful tool for zero-day attack detection.

Interlaced Magnetic Recording (IMR) is an emerging recording technology for hard-disk drives (HDDs) that provides larger storage capacity at a lower cost. By partially overlapping (interlacing) each bottom track with two adjacent top tracks, IMR-based HDDs successfully increase the data density while incurring some hardware write constraints. To update each bottom track, the data on two adjacent top tracks must be read and rewritten to avoid losing their valid data, resulting in additional overhead for performing read-modify-write (RMW) operations. Therefore, researchers have proposed various data management schemes to mitigate such overhead in recent years, aiming at improving the write performance. However, these designs have not taken into account the data characteristics of the file system, which is a crucial layer of operating systems for storing/retrieving data into/from HDDs. Consequently, the write performance improvement is limited due to the unawareness of spatial locality and hotness of data. This paper proposes a file-system-aware data management scheme called FSIMR to improve system write performance. Noticing that data of the same directory may have higher spatial locality and are mostly updated at the same time, FSIMR logically partitions the IMR-based HDD into fixed-sized zones; data belonging to the same directory will be arranged to one zone to reduce the time of seeking to-be-updated data (seek time). Furthermore, cold data within a zone are arranged to bottom tracks and updated in an out-of-place manner to eliminate RMW operations. Our experimental results show that the proposed FSIMR could reduce the seek time by up to 14% without introducing additional RMW operations, compared to existing designs.

Recently, the value of data has been widely recognized, which highlights the significance of data-centric computing in diversified application scenarios. In many cases, the data are multidimensional, and the management of multidimensional data often confronts greater challenges in supporting efficient data access operations and guaranteeing the space utilization. On the other hand, while many existing index data structures have been proposed for multidimensional data management, however, their designs are not fully optimized for modern nonvolatile memories, in particular the byte-addressable persistent memories. As a result, they might undergo serious access performance degradation or fail to guarantee space utilization. This observation motivates the redesigning of index data structures for multidimensional point data on modern persistent memories, such as the phase-change memory. In this work, we present the WARM-tree , a m ultidimensional t ree for r educing the w rite a mplification effect, for multidimensional point data. In our evaluation studies, as compared to the bucket PR quadtree and R*-tree, the WARM-tree can provide any worst-case space utilization guarantees in the form of \(\frac{m-1}{m}\) ( m ∈ ℤ^+) and effectively reduces the write traffic of key insertions by up to 48.10% and 85.86%, respectively, at the price of degraded average space utilization and prolonged latency of query operations. This suggests that the WARM-tree is a potential multidimensional index structure for insert-intensive workloads.

With advances in social engineering tricks and other technical shortcomings, ransomware attacks have become a severe cybercrime affecting organizations of all shapes and sizes. Although the security teams are making plenty of ransomware detection tools, the ransomware incident report shows they are ineffective in detecting emerging ransomware attacks. This work presents “RTrap,” a systematic framework to detect and contain ransomware efficiently and effectively via machine learning-generated deceptive files. Using a data-driven decoy file selection and generation strategy, RTrap plants deceptive decoy files across the directory to lure the ransomware to access it. RTrap also introduced a lightweight decoy watcher to monitor generated decoy files in real time. As the timing of the ransomware attack is not known to the victim in advance, and the ransomware encryption process is speedy, the proposed decoy-watcher executes an automatic/automated response after the detection promptly. The experiment shows that RTrap can detect ransomware with an average 18 file loss per 10311 legitimate user files.

Many prior research works have been widely discussed how to bring machine learning algorithms to embedded systems. Because of resource constraints, embedded platforms for machine learning applications play the role of a predictor. That is, an inference model will be constructed on a personal computer or a server platform, and then integrated into embedded systems for just-in-time inference. With the consideration of the limited main memory space in embedded systems, an important problem for embedded machine learning systems is how to efficiently move inference model between the main memory and a secondary storage (e.g., flash memory). For tackling this problem, we need to consider how to preserve the locality inside the inference model during model construction. Therefore, we have proposed a solution, namely locality-aware random forest (LaRF), to preserve the inter-locality of all decision trees within a random forest model during the model construction process. Owing to the locality preservation, LaRF can improve the read latency by 81.5% at least, compared to the original random forest library.

Intermittent systems are usually energy-harvesting embedded systems that harvest energy from ambient environment and perform computation intermittently. Due to the unreliable power, these intermittent systems typically adopt different checkpointing strategies for ensuring the data consistency and execution progress after the systems are resumed from unpredictable power failures. Existing checkpointing strategies are usually suitable for bare-metal intermittent systems with short run time. Due to the improvement of energy-harvesting techniques, intermittent systems are having longer run time and better computation power, so that more and more intermittent systems tend to function with a microkernel for handling more/multiple tasks at the same time. However, existing checkpointing strategies were not designed for (or aware of) such microkernel-based intermittent systems that support the running of multiple tasks, and thus have poor performance on preserving the execution progress. To tackle this issue, we propose a design, called self-adaptive checkpointing strategy (SACS), tailored for microkernel-based intermittent systems. By leveraging the time-slicing scheduler, the proposed design dynamically adjust the checkpointing interval at both run time and reboot time, so as to improve the system performance by achieving a good balance between the execution progress and the number of performed checkpoints. A series of experiments was conducted based on a development board of Texas Instrument (TI) with well-known benchmarks. Compared to the state-of-the-art designs, experiment results show that our design could reduce the execution time by at least 46.8% under different conditions of ambient environment while maintaining the number of performed checkpoints in an acceptable scale.

Recently, the requirement of storing digital data has been growing rapidly; however, the conventional storage medium cannot satisfy these huge demands. Fortunately, thanks to biological technology development, storing digital data into deoxyribonucleic acid (DNA) has become possible in recent years. Furthermore, because of the attractive features (e.g., high storing density, long-term durability, and stability), DNA storage has been regarded as a potential alternative storage medium to store massive digital data in the future. Nevertheless, reading and writing digital data over DNA requires a series of extremely time-consuming processes (i.e., DNA sequencing and DNA synthesis). More specifically, among the two costs, the writing cost is the predominant cost of a DNA data storage system. Therefore, to enable efficient DNA storage, this article proposes an index management scheme for reducing the number of accesses to DNA storage. Additionally, this article introduces a new DNA data encoding format with VERA (Version Editing Recovery Approach) to reduce the total writing bits while inserting and deleting the data. To the best of our knowledge, this work is the first work to provide a total data management solution for DNA storage. According to the experimental results, the proposed design with VERA can reduce the cost by 77% and improve the performance by 71% compared to the append-only methods.

The efficiency of secure deletion is highly dependent on the data layout of underlying storage devices. In particular, owing to the sequential-write constraint of the emerging Shingled Magnetic Recording (SMR) technology, an improper data layout could lead to serious write amplification and hinder the performance of secure deletion. The performance degradation of secure deletion on SMR drives is further aggravated with the need to securely erase the file system metadata of deleted files due to the small-size nature of file system metadata. Such an observation motivates us to propose a secure-deletion and SMR-aware space allocation (SSSA) strategy to facilitate the process of securely erasing both the deleted files and their metadata simultaneously. The proposed strategy is integrated within the widely-used extended file system 4 (ext4) and is evaluated through a series of experiments to demonstrate the effectiveness of the proposed strategy. The evaluation results show that the proposed strategy can reduce the secure deletion latency by 91.3% on average when compared with naive SMR-based ext4 file system.

Random forest has been widely used to classifying objects recently because of its efficiency and accuracy. On the other hand, nonvolatile memory has been regarded as a promising candidate to be a part of a hybrid memory architecture. For achieving the higher accuracy, random forest tends to construct lots of decision trees, and then conducts some post-pruning methods to fell low contribution trees for increasing the model accuracy and space utilization. However, the cost of writing operations is always very high on non-volatile memory. Therefore, writing the to-be-pruned trees into non-volatile memory will significantly waste both energy and time. This work proposed a framework to ease such hurt of training a random forest model. The main spirit of this work is to evaluate the importance of trees before constructing it, and then adopts different writing modes to write the trees to the non-volatile memory space. The experimental results show the proposed framework can significantly mitigate the waste of energy with high accuracy.

Intermittent systems enable continuous and accumulative process execution under constraint or unstable power supply. To enable intermittent computing, process status and data are typically checkpointed from volatile memory (VM) to nonvolatile memory (NVM) before running out of power. After power resumes, these logged data can be loaded back from NVM to VM for continuous execution. Nevertheless, existing approaches rarely considered the energy consumed during moving data and may waste precious power resource over data movement, instead of computation. Such observation motivates us to propose an energy-reduction on-chip memory management (ERCM2) scheme to utilize the high cell density and non-volatility of SpinTransfer Torque RAM (STT-RAM) for enabling a hybrid on chip memory architecture. The experimental results show that the proposed scheme can achieve the access performance close to conventional SRAM-based on-chip memory architecture with lower energy consumption.

Recently, nonvolatile random-access memory (NVRAM) has been regarded as the most up-and-coming main memory technology in embedded and Internet-of-Things (IoT) systems due to its attractive features: zero-static power consumption and high memory cell density. However, the endurance issue as a “nightmare” always haunts NVRAM system developers. Worse still, NVRAM’s lifespan will wear out soon in embedded applications because their data management systems usually utilize an indexing scheme to maintain small data. Plus, a node structure within the indexing scheme will be frequently updated because of data creation and deletion. Therefore, many previous works rethink B+-tree indexing scheme on an NVRAM-based system. The most previous studies focused on reducing the amount of write traffic to memory. Unfortunately, they are failed to extend the NVRAM lifespan because their solution cannot evenly distribute the amount of write traffic to each memory cell. Additionally, prior solutions have not considered that all nodes within B+-tree indexing structure have different update frequencies. Based on such the observation, this work proposes a wear-leveling-aware B+-tree design, namely, waB+-tree, to consider the update frequency of each node within the B+-tree structure, so as to evenly scatter the amount of write traffic to the NVRAM cells. According to our experiments, the proposed waB+-tree shows the encouraging results of endurance improvement.

Due to cyber-physical systems, a large-scale multiversion indexing scheme has garnered significant attention in recent years. However, modern multiversion indexing schemes have significant drawbacks (e.g., heavy write traffic and weak key- or version-range-query performance) while being applied to a computer system with a nonvolatile random access memory (NVRAM) as its main memory. Unfortunately, with the considerations of high memory cell density and zero-static power consumption, NVRAM has been regarded as a promising candidate to substitute for dynamic random access memory (DRAM) in future computer systems. Therefore, it is critical to make a multiversion indexing scheme friendly for an NVRAM-based system. For tackling this issue with modern multiversion indexing schemes, this article proposes a write-reduction multiversion indexing scheme with efficient dual-range queries. According to the experiments, our scheme effectively reduces the amount of write traffic generated by the multiversion indexing scheme to NVRAM. It offers efficient dual-range queries by consolidating the proposed version forest and the multiversion tree.

With the latest advance in the non-volatile random-access memory (NVRAM), NVRAM is widely considered as the mainstream for the next-generation storage mediums. NVRAM has numerous attractive features, which include byte addressability, limited idle energy consumption, and great read/write access speed. However, owing to the high manufacturing cost of NVRAM, the incentive of deploying NVRAM in consumer electronics is lowered due to the consideration of profitability. To resolve the profitability issue and bring the benefits of NVRAM into the design of consumer electronics, avoiding storing duplicate data on NVRAM becomes a crucial task for lowering the demand and deployment cost of NVRAM. Such observation motivates us to propose a data deduplication extended file system design (DeEXT) to boost the profitability of NVRAM via the concept of dual-chunking data deduplication while considering the characteristics of NVRAM and duplicate data content. The proposed DeEXT was then evaluated by real-world data deduplication traces with encouraging results.

Log-Structured Merge-Tree (LSM-tree) based key-value store applications have gained popularity due to their high write performance. To further pursue better performance for key-value applications, various researches were conducted by adopting different architectures of flash devices, such as key-value solid-state drives (KVSSDs). However, since LSM-trees were originally designed based on the architecture of hard disk drives (HDDs), true potential of SSDs can not be well exploited without re-designing the management strategy. In this work, we propose Parallel-Log-Single-Compaction-Tree (PLSC-tree), which is a two-level and flash-friendly key-value management strategy specially tailored for KVSSDs. In particular, the first layer takes advantage of the massive internal parallelism of SSDs for maximizing the write performance via logging, while the second layer is designed to alleviate the internal recycling (i.e., compaction) overheads of flash devices for ultimately optimizing the performance on managing key-value pairs. A series of experiments were conducted based on a well-known SSD simulator with realistic workloads, and the results are very encouraging.

Owing to the explosive growth of data volume, high areal density storage technologies have been proposed in the past few years. Among them, shingled magnetic recording (SMR) has been regarded as the most promising candidate to replace current conventional hard disk drive based on the perpendicular magnetic recording technology. However, SMR technology not only brings large capacity storage devices but also results in terrible random access performance. For increasing the random access performance of SMR, solid-state hybrid drive (SSHD) seems a possible solution in storage system development. Nevertheless, when an SMR-based SSHD is adopted to a large-scale data management system, a severe performance degeneration will happen because an indexing scheme for access efficiency always maintains data in the large-scale data management system. More specifically, jointly managing indexing keys and data values on an SSHD drive will result in the massive amount of write amplification because of read-merge-write operations and garbage collection processes. Based on such motivations, this work proposed a total solution, namely XsB+-tree, to establish a high-performance B+-tree-based data management scheme for key-value store systems. To the best of our knowledge, this work is the first work to discuss the total solution for the key-value store over an SMR-based SSHD. According to our experimental results, XsB+-tree can improve the access time by 80% on average and prolong the lifetime of SSD up to 19%.

Owing to flash memory constraints, a garbage collection (GC) mechanism hurts flash storage lifespan and performance since it generates a massive amount of write data to flash memory. To add insult to injury, all GC designs cannot identify disused data from valid data; therefore, all valid data, including disused data, will be rewritten to flash memory during the GC process. Fortunately, a flash storage vendor recently proposed a new write command to bring extra information to flash translation layer (FTL). Thanks to the new write command, the lifetime information of data can be brought from a host-side system to an FTL management layer for disused data identification. By such observations, this work proposes a dual-time referencing FTL (DTR-FTL) design to deal with disused data and minimize the overhead of GC by referring to data lifetime information and block retention time.

In the last couple of years, the move to cyberspace provides a fertile environment for ransomware criminals like ever before. Notably, since the introduction of WannaCry, numerous ransomware detection solution has been proposed. However, the ransomware incidence report shows that most organizations impacted by ransomware are running state of the art ransomware detection tools. Hence, an alternative solution is an urgent requirement as the existing detection models are not sufficient to spot emerging ransomware treat. With this motivation, our work proposes "DeepGuard," a novel concept of modeling user behavior for ransomware detection. The main idea is to log the file-interaction pattern of typical user activity and pass it through deep generative autoencoder architecture to recreate the input. With sufficient training data, the model can learn how to reconstruct typical user activity (or input) with minimal reconstruction error. Hence, by applying the three-sigma limit rule on the model's output, DeepGuard can distinguish the ransomware activity from the user activity. The experiment result shows that DeepGuard effectively detects a variant class of ransomware with minimal false-positive rates. Overall, modeling the attack detection with user-behavior permits the proposed strategy to have deep visibility of various ransomware families.

Nonvolatile random access memory (NVRAM) is becoming a popular alternative as the memory and storage medium in battery-powered embedded systems because of its fast read/write performance, byte-addressability, and nonvolatility. A well-known example is phase-change memory (PCM) that has much longer life expectancy and faster access performance than NAND flash. When NVRAM is considered as both main memory and storage in battery-powered embedded systems, existing page cache mechanisms have too many unnecessary data movements between main memory and storage. To tackle this issue, we propose the concept of “union page cache,” to jointly manage data of the page cache in both main memory and storage. To realize this concept, we design a partial page cache strategy that considers both main memory and storage as its management space. This strategy can eliminate unnecessary data movements between main memory and storage without sacrificing the data integrity of file systems. A series of experiments was conducted on an embedded platform. The results show that the proposed strategy can improve the file accessing performance up to 85.62% when PCM used as a case study.

In today's information-driven world, data access latency accounts for the expensive part of processing user requests. One potential solution to access latency is prefetching, a technique to speculate and move future requests closer to the processing unit. However, the block access requests received by the storage device show poor spatial locality because most file-related locality is absorbed in the higher layers of the memory hierarchy, including the CPU cache and main memory. Besides, the utilization of multithreading results in an interleaved access request making prefetching at the storage level more picky using existing prefetching techniques. Toward this, we propose and assess DeepPrefetcher, a novel deep neural network inspired context-aware prefetching method that adapts to arbitrary memory access patterns. DeepPrefetcher learns the block access pattern contexts using distributed representation and leverage long short-term memory learning model for context-aware data prefetching. Instead of using the logical block address (LBA) value directly, we model the difference between successive access requests, which contains more patterns than LBA value for modeling. By targeting access pattern sequence in this manner, the DeepPrefetcher can learn the vital context from a long input LBA sequence and learn to predict both the previously seen and unseen access patterns. The experimental result reveals that DeepPrefetcher can increase an average prefetch accuracy, coverage, and speedup by 21.5%, 19.5%, and 17.2%, respectively, contrasted with the baseline prefetching strategies. Overall, the proposed prefetching approach surpasses other schemes in all benchmarks, and the outcomes are promising.

Modern nonvolatile memories (NVMs) are widely recognized as energy-efficient replacements of classical memory/storage media, such as SRAM, DRAM, and mechanical hard disk. Among the popular NVMs, the skyrmion racetrack memory (SK-RM) is well known for its high storage density and unique supports of insert/delete operations. However, the existing algorithms designed for classical media might experience serious performance degradation when working on the SK-RM, due to the distinct characteristics of SK-RM. Thus, the existing algorithms should be redesigned to adapt to the brand-new memory model based on the SK-RM, so as to fully reveal the potentials of SK-RM. In particular, many existing algorithms tend to access the in-memory data in a random-hopping fashion, which generates many time-consuming shift operations of SK-RM. It is therefore crucial for the existing algorithms to eliminate unnecessary shift operations of SK-RM to boost the performance of the algorithms. In many modern applications, such as multimedia and data analysis, it is a common operation to process two or more arrays/vectors of data to perform certain computation tasks. In the arrays/vectors, an appropriate data placement strategy is critical for avoiding unnecessary shift operations of SK-RM. The observation thus motivates this work in proposing a recursive back-to-back data placement manner to effectively reduces the shift operations of SK-RM. To demonstrate the back-to-back data placement, we take sorting algorithms as a case study, and propose a novel shift-limited sorting algorithm for SK-RM. Analytical studies show that the shift-limited sort effectively enhances the time complexity of classical merge sort from O(dn lg n) to O(n lg n), where d is the bit distance between adjacent access ports on the nanotracks of the SK-RM. After that, the efficacy of the proposed shift-limited sort is then verified by experimental studies, where the results are encouraging.

Nonvolatile random access memory (NVRAM) has been regarding a promising technology to replace DRAM as the main memory in embedded systems owing to its nonvolatility and low idle power consumption. However, due to the asymmetric read/write costs and limited lifetime of NVRAM, most of the existing fundamental algorithms are not NVRAM-friendly with their write pattern and write intensiveness. Thus, existing fundamental algorithms for NVRAM embedded devices has been revealed. For instance, as the sorting algorithm is one of the most fundamental algorithms, most of the existing sorting algorithms are not NVRAM-friendly because they impose heavy write traffic [i.e., O(n lgn)] on main memory, where n is the number of unsorted elements. To resolve this issue, this article proposes a write-once sorting algorithm, namely B*-sort, to reduce the amount of write traffic on NVRAM-based main memory. B*sort adopts a brand-new concept, i.e., tree-based sort, inspired by the binary-search-tree structure to achieve the write-once property which can guarantee the optimal endurance during the sorting process. According to the experimental results, B*-sort can achieve significant performance improvement for sorting on NVRAM-based systems.

Shingled magnetic recording (SMR) is regarded as a promising technology for resolving the areal density limitation of conventional magnetic recording hard disk drives. Among different types of SMR drives, drive-managed SMR (DM-SMR) requires no changes on the host software and is widely used in today’s consumer market. DM-SMR employs a shingled translation layer (STL) to hide its inherent sequential-write constraint from the host software and emulate the SMR drive as a block device via maintaining logical to physical block address mapping entries. However, because most existing STL designs do not simultaneously consider the access pattern and the data update frequency of incoming workloads, those mapping entries maintained within the STL cannot be effectively managed, thus inducing unnecessary performance overhead. To resolve the inefficiency of existing STL designs, this article proposes a demand-based STL (DSTL) to simultaneously consider the access pattern and update frequency of incoming data streams to enhance the access performance of DM-SMR. The proposed design was evaluated by a series of experiments, and the results show that the proposed DSTL can outperform other SMR management approach by up to 86.69% in terms of read/write performance.

To meet the requirement of low-power consumption, multi-level-cell STT-RAM (MLC STT-RAM) has been widely regarded as a potential candidate for replacing DRAM-based main memory in the next generation computer architectures because of its high memory cell density, fast read/write performance and zero refresh power consumption. However, MLC STT-RAM has higher power consumption than DRAM while a write operation is performed because MLC STT-RAM sometimes needs to perform a two-step transition to change the originally stored bits to another specifically written bit patterns. As a result, MLC STT-RAM has different power consumption while different bit patterns are written to a memory cell. To the best of our knowledge, a few or none of the previous studies rethink a cache replacement policy to overcome the asymmetric write energy issue of MLC STT-RAM-based main memory. Thus, this study proposes an energy-aware cache replacement policy, namely E-cache, which considers asymmetric write-back power consumption on MLC STT-RAM-based main memory to evict a proper cached data from the last-level cache, so as to minimize system power consumption. The experimental results show that the proposed solution reduces the energy consumption by 36% on average, compared with the LRU.

Growing demand for key-value store applications is building a strong momentum for the commercialization of key-value hard disk drives. To achieve better performance, flash-based solid state drive is the next ideal candidate for commercialization in the foreseeable future. However, the existing fixed-sized management strategies of flash-based devices would potentially result in low storage space utilization when managing variable-sized key-value data. In addition, the low storage space utilization would further lead to the degradation of device performance, due to low invalid data space reclamation efficiency. The space utilization issue motivates this paper to propose a key-value flash translation layer design to improve storage space utilization as well as the performance of the key-value solid state drives. A series of experiments was conducted to evaluate the proposed design, and the experiment results of space utilization and device performance are very encouraging.

When a shingle magnetic recording (SMR) drive has been widely applied to modern computer systems (e.g., archive file systems, big data computing systems, and large-scale database systems), storage system developers should thoroughly review whether current designs (e.g., index schemes and data placements) are appropriate for an SMR drive because of its sequential write constraint. Through many prior works excellently manage data in an SMR drive by integrating their proposed solutions into the driver layer, an index scheme over an SMR drive has never been optimized by any previous works because managing index over the SMR drive needs to jointly consider the properties of B + -tree and SMR natures (e.g., sequential write constraint and zone partitions) in a host storage system. Moreover, poor index management will result in terrible storage performance because an index manager is extensively used in file systems and database applications. For optimizing the B + -tree index structure over an SMR storage, this work identifies performance overheads caused by the B + -tree index structure in an SMR drive. By such observation, this study proposes a sequential-write-constrained B + -tree index scheme, namely SW-B + tree, which consists of an address redirection data structure, an SMR-aware node allocation mechanism, and a frequency-aware garbage collection strategy. According to our experiments, the SW-B + tree can improve the SMR storage performance 55% on average.

At present, nonvolatile random access memory (NVRAM) is widely considered as a promising candidate for the next-generation storage medium due to its appealing characteristics, including short read/write latency, byte addressability, and low idle energy consumption. In addition, to provide a higher bit density, multilevel-cell (MLC) NVRAM has also been proposed. Nevertheless, when compared with conventional single-level-cell (SLC) NVRAM, MLC NVRAM has longer write latency and higher energy consumption. Hence, the performance of MLC NVRAM-based storage systems could be degraded due to the lengthened write latency. The performance degradation is further magnified by existing journaling file systems (JFS) on MLC NVRAM-based storage devices due to the JFS's fail-safe policy of writing the same data twice. Such observations motivate us to propose multiwrite-mode JFSs (mwJFSs) to alleviate the drawbacks of MLC NVRAM and boost the performance of MLC NVRAM-based JFS. The proposed mwJFS differentiates the data retention requirement of journaled data and applies different write modes to enhance the access performance with lower energy consumption. A series of experiments was conducted to demonstrate the capability of mwJFS on MLC NVRAM-based storage systems.

Due to the fast access performance, byte-addressability, and non-volatility of non-volatile random access memory (NVRAM), NVRAM has emerged as a popular candidate for the design of memory/storage systems on mobile computing systems. For example, the latest 3D xPoint memory could be a kind of NVRAM with much longer life expectancy than NAND flash and could ease the possible endurance issue. When NVRAM is considered as both main memory and storage in mobile computing systems, existing page cache mechanisms introduce too many unnecessary data movements between main memory and storage. To resolve this issue, we propose the concept of "union page cache," which jointly manages data of the page cache in both main memory and storage. To realize this concept, a partial page cache strategy is designed to consider both main memory and storage as its management space and to eliminate unnecessary data movements between main memory and storage without sacrificing the data consistency of file systems. Experimental results show that the proposed strategy can boost the file accessing performance upto 85.62% when using PCM as a case study.

Due to the decreasing endurance of flash chips, the lifetime of flash drives has become a critical issue. To resolve this issue, various techniques such as wear-leveling and error correction code have been proposed to reduce the bit error rates of flash storage devices. In contrast to these techniques, we observe that minimizing write amplification is another promising direction to enhance the lifetime of a flash storage device. However, the development trend of large-page flash memory exacerbates the write amplification issue. In this work, we present a compression-based management design to deal with compressed data updates and internal fragmentation in flash pages. Thus, it can minimize write amplification by only updating the modified part of flash pages with the support of data reduction techniques; and the reduced write amplification degree is more significant when the flash page size becomes larger due to the development trend. This design is orthogonal to wear-leveling and error correction techniques and thus can cooperate with them to further enhance the lifetime of a flash device. Based on a series of experiments, the results demonstrate that the proposed design can effectively improve the lifetime of a flash storage device by reducing write amplification.

Non-volatile random-access memory (NVRAM) is regarded as a great alternative storage medium owing to its attractive features, including low idle energy consumption, byte addressability, and short read/write latency. In addition, multi-level-cell (MLC) NVRAM has also been proposed to provide higher bit density. However, MLC NVRAM has lower energy efficiency and longer write latency when compared with single-level-cell (SLC) NVRAM. These drawbacks could lead to higher energy consumption of MLC NVRAM-based storage systems. The energy consumption is magnified by existing journaling file systems (JFS) on MLC NVRAM-based storage devices due to the JFS's fail-safe policy of writing the same data twice. Such observations motivate us to propose a multi-write-mode journaling file systems (mwJFS) to alleviate the drawbacks of MLC NVRAM and lower the energy consumption of MLC NVRAM-based JFS. The proposed mwJFS differentiates the data retention requirement of journaled data and applies different write modes to enhance the energy efficiency with better access performance. A series of experiments was conducted to demonstrate the capability of mwJFS on a MLC NVRAM-based storage system.

Non-volatile random-access memory (NVRAM) becomes a mainstream storage device in embedded systems due to its favorable features, such as small size, low power consumption, and short read/write latency. Unlike dynamic random access memory (DRAM), NVRAM has asymmetric performance and energy consumption on read/write operations. Generally, on NVRAM, a write operation consumes more energy and time than a read operation. Unfortunately, current mobile/embedded file systems, such as EXT2/3 and EXT4, are very unfriendly for NVRAM devices. The reason is that current mobile/embedded file systems employ a journaling mechanism for increasing its data reliability. Although a journaling mechanism raises the safety of data in a file system, it also repeatedly writes data to a data storage while data is committed and checkpointed. Though several related works have been proposed to reduce the amount of write traffic to NVRAM, they still cannot effectively minimize the write amplification of a journaling mechanism. Such observations motivate us to design a two-phase write reduction journaling file system called wrJFS. In the first phase, wrJFS classified data into two categories: Metadata and user data. As the size of metadata is usually very small (few bytes), byte-enabled journaling strategy will handle metadata during commit and checkpoint stages. In contrast, the size of user data is very large relative to metadata; thus, user data will be processed in the second phase. In the second phase, user data will be compressed by hardware encoder to reduce the write size and managed compressed-enabled journaling strategy to avoid the write amplification on NVRAM. Moreover, we analyze the overhead of wrJFS and show that the overhead is negligible. According to the experimental results, the proposed wrJFS outperforms other journaling file systems even though the experiments include the overhead of data compression.

Owing to the fast-growing demands of larger and faster NAND flash devices, new manufacturing techniques have accelerated the down-scaling process of NAND flash memory. Among these new techniques, 3D charge trap flash is considered to be one of the most promising candidates for the next-generation NAND flash devices. However, the long erase latency of 3D charge trap flash becomes a critical issue. This issue is exacerbated because the distinct transient voltage shift phenomenon is worsened when the number of program/erase cycle increases. In contrast to existing works that aim to tackle the erase latency issue by reducing the number of block erases, we tackle this issue by utilizing the “multi-block erase” feature. In this work, an erase efficiency boosting strategy is proposed to boost the garbage collection efficiency of 3D charge trap flash via enabling multi-block erase inside flash chips. A series of experiments was conducted to demonstrate the capability of the proposed strategy on improving the erase efficiency and access performance of 3D charge trap flash. The results show that the erase latency of 3D charge trap flash memory is improved by 75.76 percent on average even when the P/E cycle reaches$10^{4}$.

With the advanced technology in persistent random access memory (PRAM), PRAM such as three-dimen-sional XPoint memory and Phase Change Memory (PCM) is emerging as a promising candidate for the next-generation medium for both (main) memory and storage. Previous works mainly focus on how to overcome the possible endurance issues of PRAM while both main memory and storage own a partition on the same PRAM device. However, a holistic software-level system design should be proposed to fully exploit the benefit of PRAM. This article proposes a union storage file system (UnistorFS), which aims to jointly manage the PRAM resource for main memory and storage. The proposed UnistorFS realizes the concept of using the PRAM resource as memory and storage interchangeably to achieve resource sharing while main memory and storage coexist on the same PRAM device with no partition or logical boundary. This approach not only enables PRAM resource sharing but also eliminates unnecessary data movements between main memory and storage since they are already in the same address space and can be accessed directly. At the same time, the proposed UnistorFS ensures the persistence of file data and sanity of the file system after power recycling. A series of experiments was conducted on a modified Linux kernel. The results show that the proposed UnistorFS can eliminate unnecessary memory accesses and outperform other PRAM-based file systems for 0.2--8.7 times in terms of read/write performance.

The strong momentum of key-value store applications drives the commercialization of key-value-specific hard disk drives. To achieve higher degree of performance, the specific flash-based solid state drives would be also commercialized for key-value store applications in the foreseeable future. However, the existing fixed-sized management strategies of flash-based devices would potentially result in low storage space utilization on managing variable-sized key-value data. This problem inspires this paper to propose a key-value flash translation layer (KVFTL) design to improve the storage space utilization of the key-value-specific solid state drives (KVSSDs). A series of experiments was conducted to evaluated the proposed design, and the experimental results on space utilization and device performance are very encouraging.

As the volume of data stored by Big data and Cloud services continues to grow, both academia and industry are seeking for high-performance storage systems. Recently, with the recent advances in write-optimized indexes (WOI), WOI-based file systems can now outperform conventional file systems with orders of magnitude on random writes, metadata updates, and small file creation. Based on the B-tree structure, WOI-based file systems can not only process data faster than the conventional B-tree but also improve the range query performance. However, the write amplification of these WOI-based file systems becomes a serious performance overhead when adopting flash storage as underlying storage devices due to the recursive entry update behavior. To mitigate the write amplification problem of WOIbased file systems, we propose a flash-friendly WOI design to reduce the number of write requests on flash storage. To evaluate the performance of the proposed design, we adapt B+-tree as a case study and the experimental results are promising.

Non-volatile memory (NVM) has widely participated in the evolution of the next-generation memory architecture by way of being the substitution of the main memory. To cope with the problem of asymmetric read/write speeds of NVM, several excellent researches have been proposed to reduce the number of writes to the NVM-based main memory. Nevertheless, most of these existing approaches do not take the cache-line-based access behavior between the processor and the main memory into consideration. Thus, in order to essentially improve the access performance of the NVM-based memory architecture, this work aims to optimize the cache-line-based access performance over the NVM-based memory architecture based on the special access patterns in many popular internet of things (IoT) and in-memory database applications. Our experiments based on the well-known Gem5 full system simulator reveal that, compared to other existing representative approaches, the proposed design can effectively reduce the total execution time of insertion by 20.92~55.20% and improve the execution time of query by 2.06~23.36%.

Non-volatile random-access memory (NVRAM) becomes a mainstream storage device in embedded systems due to its favorable features, such as small size, low power consumption, and short read/write latency. On NVRAM, a write operation consumes more energy and time than a read operation. However, current mobile/embedded file systems (e.g., EXT2/3 and EXT4) are very unfriendly for NVRAM devices. The reason is that a journaling mechanism writes the same data twice during data commitment and checkpoint. Such observations motivate this paper to design a two-phase write reduction journaling file system called wrJFS. In the first phase, wrJFS classified data into two categories: Metadata and user data. Metadata will be handled by partial byte-enabled journaling strategy, and user data will be processed in the second phase. In the second phase, user data will be compressed by hardware encoder so as to reduce the write size, and managed compressed-enabled journaling strategy to avoid the write amplification. The experimental results show that the proposed wrJFS can reduce the size of the write request by 89.7% on average, compared with the original EXT3.

The growing demands of large capacity fash-based storages have facilitated the down-scaling process of NAND fash memory. Among NAND fash technologies, 3D charge trap fash is regarded as one of the most promising candidates. Owing to the cylindrical geometry of vertical channels, the access performance of each page in one block is distinctive, and this situation is exaggerated in the 3D charge trap fash with the fast-growing number of layers. In this study, a progressive performance boosting strategy is proposed to boost the performance of 3D charge trap fash by utilizing its asymmetric page access speed feature. A series of experiments was conducted to demonstrate the capability of the proposed strategy on improving access performance of 3D charge trap flash.

In our previous work, a simulation framework was proposed to focus on imitating the behavior of wireless charging vehicles (WCVs) and wireless sensor networks (WSNs) because current mainstream simulators have very limited support on simulation of WCVs. The WCV is an integration of a mobile vehicle and a wireless power transfer broadcaster, which is used to recharge sensors wirelessly to prolong the lifetime of sensor networks. In the study of WCVs, simulators are extensively used to study the routing algorithms and behaviors of WCVs because it is very costly to build a WSN testbed and many specifications are not standardized. However, mainstream WSN simulators require researchers to develop and integrate their WCV modules. Therefore, the previously proposed framework aims to provide a simple framework for simulating of wireless power transfer and mobile vehicles. In this study, to further strength the usability of the proposed simulation framework, a graphic user interface is introduced to allow users to assign sensors' location and specify simulation parameters.

To accommodate the sheer volume of data in the era of Big Data and Cloud Computing, both new storage medium technologies and high-performance file systems are proposed. For storage medium, Shingled Magnetic Recording (SMR) increases the areal density by overlapping adjacent tracks so as to provide larger storage capacity. On the other hand, write-optimized indexes (WOI) file systems are also studied and can now outperform conventional file systems with orders of magnitude. However, the main drawback of SMR is the random-write restriction because random-write operations will cause the extra overhead of rewriting data stored in overlapped tracks. The rewriting overhead is amplified by the recursive entry update behavior of WOI-based file systems. Therefore, the rewriting issue becomes a serious performance overhead when adopting SMR drives as underlying storage devices for WOI-based file systems. To mitigate the write amplification problem when deploying WOI-based file systems on SMR disks, this paper proposes the update-overhead-aware caching policy to reduce the update overhead with the help of flash-based storage devices. To evaluate the performance of the proposed design, the B+-tree as a case study. The experimental results are promising.

In this live demonstration, we would like to present a simulation framework for simulating the behaviors of Wireless Sensor Network (WSN) and Wireless Charging Vehicle (WCV). Different to general purpose WSN simulators, the proposed simulation framework focuses on the simulation of mobile vehicles and wireless power transfer techniques. Besides, the proposed framework provides an easy-to-use user interface and a well structured system architecture. The proposed framework aims to eliminate the need for researchers to build their own simulator or integrate wireless charging modules, allowing them directly to evaluate their algorithm and compare the simulation results.

Since the mid-2000s, mobile/embedded computing systems conventionally have limited computing power, Random Access Memory (RAM) space, and storage capacity due to the consideration of their cost, energy consumption, and physical size. Recently, some of these systems, such as mobile phone and embedded consumer electronics, have more powerful computing capability, so they manage their data in small flash storage devices (e.g., Embedded Multi Media Card (eMMC) and Secure Digital (SD) cards) with a simple file system. However, the existing file systems usually have low space utilization for managing small files and the tail data of large files. In this work, we thus propose a dynamic tail packing scheme to enhance the space utilization of file systems over flash storage devices in embedded computing systems by dynamically aggregating/packing the tail data of (small) files together. To evaluate the benefits and overheads of the proposed scheme, we theoretically formulate analysis equations for obtaining the best settings in the dynamic tail packing scheme. Additionally, the proposed scheme was implemented in the file system of Linux operating systems to evaluate its capability. The results demonstrate that the proposed scheme could significantly improve the space utilization of existing file systems.

The support of secure deletion on formatting a file system is to make sure that when a file system is formatted, there is no way to get any file content back again. Due to the fast-growing storage capacity, the performance of secure deletion to file systems on resource-constrained flash storage devices has become a critical issue. In contrast to the existing works that take a long time on overwriting/resetting all the file contents of a file system, we propose an efficient secure deletion scheme to securely delete all the contents of a file system without rewriting file contents. Thus, secure deletion to file systems can be efficiently achieved and can be independent of the device capacity and file systems. A series of experiments was conducted with realistic workloads to evaluate the capability of the proposed scheme. The results show that the proposed scheme achieves secure deletion with limited performance overheads in most cases.

Phase-change memory (PCM) is a promising candidate as a storage medium to resolve the performance gap between main memory and storage in battery-powered mobile computing systems. However, it is more expensive than flash memory, and thus introduces a more serious storage capacity issue for low-cost solutions. This issue is further exacerbated by the fact that existing file systems are usually designed to trade space utilization for performance over block-oriented storage devices. In this work, we propose a multi-grained block management strategy to improve the space utilization of file systems over PCM-based storage systems. By utilizing the byte-addressability and fast read/write feature of PCM, a methodology is proposed to dynamically allocate multiple sizes of blocks to fit the size of each file, so as to resolve the space fragmentation issue with minimized space and management overheads. The space utilization of file systems is analyzed with consideration of block sizes. A series of experiments was conducted to evaluate the efficacy of the proposed strategy, and the results show that the proposed strategy can significantly improve the space utilization of file systems.

Recently, phase change memory (PCM) has become a promising candidate to replace dynamic RAM as main memory due to its low power consumption, fast I/O performance, and byte addressability. Accompanied with the merits, the adoption of PCM may suffer from its physical characteristic of limited write endurance. Wear leveling is a well-known approach to address this issue. For PCM main memory, the design of wear leveling should stress operation efficiency and overhead reduction. Nevertheless, conventional designs are usually dedicated to prolonging the lifetime of PCM in the best effort. In this paper, we propose a novel perspective that, instead of valuing PCM lifetime exploitation as the first priority, we turn to satisfy the product warranty period. With such a paradigm shift, the management overhead of wear-leveling mechanisms could be reduced so as to achieve further enhancement of operation efficiency. To this end, we propose a warranty-aware page management design that introduces novel criteria used to determine the state of a page by taking both the product warranty period and the write cycles of a page into consideration. Theoretical analysis is also conducted to investigate the properties and performance of the proposed management. To show the effectiveness of the proposed design, we collected real traces by running SPEC2006 benchmarks with different write intensity workloads. The experimental results showed that our design reduced the overhead to one-third that of the state-of-the-art designs while still providing the same level of performance.

Recently, many applications and users rely on cloud storage services, such as Google drive, Dropbox, iCloud and Sky drive, to store private files and system data, and cloud storage services must thus be reliable and secure. To increase reliability, previous studies have proposed a variety of erasure coding algorithms for data fault tolerance for use in storage systems. Although these data fault tolerance mechanisms increase data reliability, implementation also increases storage system costs and energy consumption due to data redundancy. However, to date energy-efficient schemes have only been developed based on a RAID architecture, and none have been implemented using an erasure coding algorithm. To address this issue, this study proposes an energy-aware I/O framework with a quality-of-service (QoS) aware data reconstruction scheduler for erasure coding algorithms, called the EEC-scheme. This approach reduces storage system energy consumption and decreases response times for user requests when the system restores failed disks. A series of experiments show that the proposed scheme can significantly reduce power consumption in storage systems.

Unlike a traditional network architecture, a software-defined networking architecture is divided into the control plane and the data plane. Network administrators use the centralized control plane to manage network authority and determine where network traffic is to be sent in the data plane. However, a centralized control structure causes a bottleneck with an overloading flow or under a DDoS attack. Under such conditions, the probability of network misconfiguration may increase rapidly and network performance may decline rapidly. This work paper proposes a hash-based mechanism that operates in the control plane to increase the reliability and scalability of the network. The hash function is utilized to assign incoming packets to queues in the control plane. The controller schedules the queues using a round-robin method to reduce the probability of failure in response to malicious attacks and to reduce transmission delay when network congestion occurs. The experimental results reveal that the proposed mechanism effectively distributes the workload and increases the reliability of the network under high-density data transmission.

The lifetime of wireless sensor networks are constrained by its limited battery capacity. Therefore, the lifetime is widely regard as a bottleneck of technique of wireless sensor network. Recently, the emerging breakthrough in wireless power transfer technique is expected to eliminate the power constraint bottleneck. In this paper, we propose an intelligent wireless charging vehicle (IWCV) strategy to resolve above problem in a dynamic and scalable approach. The IWCV strategy includes an intelligent routing strategy to traverse the sensor network topology and charging their battery to prolong their lifetime. What makes IWCV different to previous studies is that IWCV can still work even if the topology changes by re-computing the traversing route and stop time for each node in a relative short amount of time, compared with the time needed to find the shortest Hamiltoaian cycle. With the scalable and dynamic feature of IWCV, one can change their sensor network topology without down time to reconfigure the wireless charging vehicle while still maintain low energy consumption during traveling and charging in dynamic network topologies.

Summary A distributed environment requires a monitoring system to oversee the operation of various distributed nodes. A monitoring service is crucial because it ensures a high‐quality computing environment and a reliable service. The interface and framework determine the effectiveness of a monitoring system. This paper uses the concept of user‐adaptive visualization to design its interface and proposes a flexible modular framework. Designers can use the proposed modular framework to flexibly extend existing modules, design visual interfaces to satisfy user requirements, and improve system failover schemes. The implementation of such a monitoring system for monitoring data preservation nodes is also provided. The system including fault‐tolerance and notification functions supports full monitoring services for Storage Resource Broker (SRB) or integrated Rule‐Oriented Data System (iRODS) based systems. The experimental results show that the proposed framework is suitable for data preservation services and is robust and responsive when faced with system failures. Copyright © 2014 John Wiley & Sons, Ltd.

Previous studies proposed energy-efficient solutions, such as multispeed disks and disk spin-down methods, to conserve power in their respective storage systems. However, in most cases, the authors did not analyze the reliability of their solutions. According to research conducted by Google and the IDEMA standard, frequently setting the disk status to standby mode will increase the disk’s Annual Failure Rate and reduce its lifespan. To resolve the issue, we propose an evaluation function called E 3 SaRC (Economic Evaluation of Energy Saving with Reliability Constraint), which considers the cost of hardware failure when applying energy-saving schemes. We also present an adaptive write cache mechanism called CacheRAID. The mechanism tries to mitigate the random access problems that implicitly exist in RAID techniques and thereby reduce the energy consumption of RAID disks. CacheRAID also addresses the issue of system reliability by applying a control mechanism to the spin-down algorithm. Our experimental results show that the CacheRAID storage system can reduce the power consumption of the conventional software RAID 5 system by 65% to 80%. Moreover, according to the E 3 SaRC measurement, the overall saved cost of CacheRAID is the largest among the systems that we compared.

Improving the disk I/O performance is always a critical research issue in cloud computing platforms, especially for cloud computing platforms with distributed data-intensive workloads. To resolve the problem of poor disk I/O, in this paper, we propose a novel scheduling framework in the Xen-based hypervisor. In our framework, we employ a locality-aware scheduler with a deadline constraint and provide a basic QoS controller to guarantee the throughput of the cloud platform. The experimental results show that our solution increases the IOPS of Xen-based cloud platform by 9%-13% compared to the solution of early-deadline-first (EDF), deadline scheduling algorithm or Flubber. Moreover, according to the schedulability test, our solution can improve the miss deadline ratio significantly, compared to the EDF scheduling algorithm and Flubber.

The thriving growth in mobile consumer electronics makes energy efficiency in the embedded system design an important and recurring theme. Phase Change Memory (PCM) has shown its potential in replacing DRAM as the main memory option due to its (65%) reduced energy requirements. However, when considering the usage of PCM main memory, its write endurance becomes a critical issue, and wear leveling design is a common approach to resolve this issue. Even though the wear leveling design should stress operation efficiency and overhead reduction, existing wear leveling strategies designed for PCM main memory are usually dedicated to prolonging the lifetime of PCM. In this paper, we propose the perspective that, instead of valuing PCM lifetime exploitation as the first priority, we should turn to satisfy the product warranty period. To this end, further enhancement of operation efficiency and reduction of management overhead could be achieved. We thus propose a warranty-aware page management design to enhance the operation efficiency for managing the endurance issue in PCM. To show the effectiveness of the proposed design, we collected real traces on fiasco. OC by running SPEC2006 benchmarks with different write intensity workloads. The experiment results showed that our design reduced the overhead to one third of that of the state-of-the-art designs while still providing the same level of performance.

Although wireless sensor devices usually have limited power, they are widely deployed in various applications, such as in remote sensing for forestry applications, military monitoring, and animal behavior. Most sensor applications deploy sensor devices in natural environments, such as forests, tunnels, and caves, to monitor targets and to collect data. To permanently monitor target environments, the battery in a sensor device needs to be recharged as its battery capacity the limited. A wireless charging vehicle uses wireless charging technology to prolong the lifetime of sensor network applications by recharging the device's battery. The wireless charging vehicle is usually equipped with a large capacity battery, an electromagnetic field, and wheels such that it can move throughout an entire sensor network to charge sensors' batteries. When the wireless charging vehicle does not need to recharge any sensor's battery, it stays at a service station to recharge its own battery. Hence, a wireless charging vehicle needs to consider two things: sensor network lifetime, and vehicle energy consumption. This work proposes a geometric solution called the Dynamic Path Generation Scheme (DPG-Scheme) to arrange the Wireless Charging Vehicle's (WCV's) travelling path while minimizing a vehicle's energy consumption and maximizing a sensor network's lifetime. The DPG-Scheme is based on the space-filling curve solution. Based on the properties of the space-filling curve, the DPG-Scheme uses space-filling curves as a space-filling curve heuristic for the NP-hard Euclidean travelling salesperson problem. The DPG-Scheme can reduce computational time when computing a wireless sensor network's (WSN's) travelling path and a new path is calculated rapidly during sensor network topology changes.

Embedded computing systems usually have limited computing power, RAM space, and storage capacity due to the consideration of their cost, energy consumption, and physical size. Some of them such as sensor nodes and embedded consumer electronics only have a small-sized flash memory as their storage with a (simple) file system to manage their data, which are usually of small sizes. However, the existing file systems usually have low space utilization on managing small files and the tail data of large files. In this work, we propose a dynamic tail packing scheme to optimize the space utilization of file systems by dynamically aggregating/packing the tail data of (small) files together. The proposed scheme was implemented in the file system of Linux operating systems to evaluate its capability. The results demonstrate that the proposed scheme could significantly improve the space utilization of existing file systems.

Flexible electronics appear in the consumer, medical, and military sectors. Thanks to the development of flexible electronics, flexible touchscreens have been widely carried on in various devices, such as mobile phones, wearable devices and hand-held tablets. Flexible touchscreens not only bring the technique of displays to next generation, but also significantly alter the interactive behaviors of users and devices. On the flexible touchscreens, when the displays are folded, some touch area around the folded line is not touchable in users' operation, and this is a critical research problem for the flexible touch screens. However, to our knowledge, little or no user interface research has solved this problem. To resolve this critical problem, in this study, we design a novel user interface, called the Auto-Adjusting Placement, which can dynamically adjust objects, such as icons, texts and pictures, on the flexible touch screens to avoid the area around the folded line and to keep the high availability/readability of the objects. Our demonstrations show that the Auto-Adjusting Placement is well performed on flexible touchscreens and therefore users have a consistent interface to use. We also filed a patent for this Auto-Adjusting Placement.

Recently, digital multimedia has become widely distributed in computer and network technology. For digital multimedia distribution applications, issues surrounding information security have received significant attention. Data hiding has been one of most researched issues in information security. In this paper, reversible video data hiding based on neighbouring similarity is proposed. Prediction encoding was used to compute the prediction errors. All prediction errors were explored to develop a histogram‐based reversible video data hiding algorithm. The results show that the proposed approach has a higher capacity and similar embedding distortion compared with other related schemes. Also, the original video frame could be recovered after the hidden information was extracted.

The concept of green storage in cluster computing has generated a great deal of interest among researchers in recent years. As a result, several energy-efficient solutions, such as multi-speed disks and disk spin down methods, have been proposed to conserve power in storage systems and improve disk access. Some researchers evaluate their solutions via simulations, while others utilize real-world experiments. Both methods have advantages and disadvantages. To address the problem, we propose an efficient simulation tool called BASE, which can accurately estimate the power consumption of disks in large-scale storage systems. We evaluate the performance of BASE on real-world traces from Academia Sinica (Taiwan) and Florida International University. BASE incorporates an analytical method for evaluating the reliability of energy-efficient solutions. Our analysis results show that the measurement error of BASE is 2.5% lower than that achieved in real-world experiments on energy estimation. Moreover, the results of simulations performed to evaluate a solution's reliability are the same as those derived by real-world experiments.

Virtualization is a critical technology issue in cloud computing. Virtualization technology faces two major challenges, namely, poor I/O throughput and long latency for data access. To address the issues, we present a distributed deadline modification SCAN mechanism called DDM-SCAN. We integrate the DDM-SCAN mechanism to Xen-based cloud platform. The result of our simulations show DDM-SCAN improve the I/O response time of Xen-based cloud platform 20% comparing to Flubber [1] mechanism and it also guarantee same or better quality of service (QoS) as compared with Flubber mechanism in Xen-based hypervisor. In advance, this paper provides more easy method to implement DDM-SCAN on Xen-based hypervisor rather than Flubber mechanism.

Internet of Things (IoT) has been widely researched over the past decade. Recently, many research results of IoT related to emergency system, smart building and medical system, etc. The key for IoT applications are the ability to interact with physical world through computation, communication, and machine control. However, each sensor device in IoT cannot conveniently communicate with other terminal devices through internet protocol. So, it is necessary to establish protocol translation stack or equipment between two WSN groups. That is very inefficient and high overhead cost of network construction. The development of micro-IP (uIP) solves this problem. The uIP reduce cost of protocol translation and it also realizes the machine to machine (M2M) concept in wireless sensor network. Therefore, this paper proposes a solution for porting uIP library to the wireless sensor network devices and presents the integration of a speaker module and IPv6 ready sensor device. We also propose a safe building application based on the integrated system to help people escaping from disaster environment. In conclusion, our contributions are building an IPv6 ready wireless sensor network environment and develop a safe building system to make the concept of IoT in IPv6 network environment come true.

Recently, to achieve privacy protection using biometrics, Fan and Lin proposed a three‐factor authentication scheme based on password, smart card and biometrics. However, the authors have found that Fan and Lin's proposed scheme (i) has flaws in the design of biometrics privacy, (ii) fails to maintain a verification table, making it vulnerable to stolen‐verifier attack and modification attack, and (iii) is vulnerable to insider attacks. Thus, the authors propose an elliptic curve cryptography‐based authentication scheme that is improved with regard to security requirements. The authors’ proposed scheme overcomes the flaws of Fan and Lin's scheme and is secured from attacks. Furthermore, the authors have presented a security analysis of their scheme to show that their scheme is suitable for the biometric systems.

The execution environment of Android system is based on a virtual machine called Dalvik virtual machine (DVM) in which the execution of an application program is in interpret-mode. To reduce the interpretation overhead of DVM, Google has included a trace-based just-in-time compiler (JITC) in the latest version of Android. Due to limited resources and the requirement for reasonable response time, the JITC is unable to apply deep optimizations to generate high quality code. In this paper, we propose a method-based ahead-of-time compiler (AOTC), called Icing, to speed up the execution of Android applications without the modification of any components of Android framework. The main idea of Icing is to convert the hot methods of an application program from DEX code to C code and uses the GCC compiler to translate the C code to the corresponding native code. With the Java Native Interface (JNI) library, the translated native code can be called by DVM. Both AOTC and JITC have their strength and weakness. In order to combine the strength and avoid the weakness of AOTC and JITC, in Icing, we have proposed a cost model to determine whether a method should be handled by AOTC or JITC during profiling. To evaluate the performance of Icing, four benchmarks used by Google JITC are used as test cases. The performance results show that, with Icing, the execution time of an application is two to three times faster than that without JITC, and 25% to 110% faster than that with JITC.

A traditional wireless sensor network is composed of several sensors and a sink. The sink analyzes data measured by the distributed sensors and takes appropriate action. A problem with this kind of architecture is that it may have a single-point of failure. Also, sensors are not connected directly to the sink and must send data by hopping through other sensors. This means that it would take more time for the sink to collect data. In a wireless sensor network, noise may distort the message during transmission. An intruder may also alter the message maliciously. So far, there has been little research done on the design of robust wireless sensor networks to overcome the single-point of failure problem and environmental interference. In this study, we propose a consensus problem algorithm based solution to enhance the accuracy of the detected result in an autonomous local sensor network without a centralized sink. Under our scheme, there is no need to send the detected value to the sink. The solution can therefore reduce the transmission and routing time, allowing appropriate action to be made directly and quickly.

Entering and leaving of random peers will result in great variance of data availability in P2P networks, especially when multimedia streams require high priority to the immediate playback data. All peers must be able to receive the complete video segment before that playback. This requirement becomes more critical in mobile and wireless network environments where mobile peers have high frequency to leave and join the P2P network. Therefore, the provision of the tracker in the P2P networks is to accurately track the status of each peer and so to maintain high data availability being considered functionally. Our work deliberates the redundant mechanism of BitTorrent Tracker and designs a BT-like redundant tracker mechanism that is configured to this purpose, and presents the relative performance measure. The result shows that the proposed redundant tracker does not increase overheads and is able to upgrade stability to the playback operations in mobile P2P streaming networks.

Real-time systems using rate-monotonic fixed priority scheduling can be checked for schedulability either by sufficient but pessimistic schedulability conditions or by exact testing. Exact testing provides a more precise result but may not be performed in polynomial time. Audsley et al. proposed one of the earliest methods by iteratively deriving the response times of jobs. Other researchers have improved the exact test method by using different initial values for testing. In this paper, we propose new initial values of p, - p, , and f in a task set of i tasks, where p, is the period of task Tl. We show that the new initial values can significantly improve the efficiency of exact testing. These period-dependent initial values can also be used for the schedulability test of multiframe task models and effectively reduce the number of iterations for testing.

The real-time multiframe task model first studied by Mok and Chen assumes that the computation times of a periodic task vary instance by instance. They have derived an utilization bound for verifying the schedulability of multiframe task sets. Their schedulability test has since been improved by other researchers. In this paper we use the information about the relative period ratios between tasks in a system to derive a new schedulability condition. By considering the smallest and the largest period values in a system, we can show that the RM schedulability bound can be improved significantly. This method also can be applied to other test methods studied earlier to improve the schedulability of real-time multiframe systems.

Real-time systems using rate monotonic fixed priority scheduling can be checked for schedulability either by pessimistic schedulability conditions or exact testing. Exact testing provides a more precise result but cannot always be performed in polynomial time. Audsley et al. proposed one of the earliest methods by iteratively deriving the job response times. Other researchers have improved the efficiency of their exact test method by using different initial values. All currently proposed initial values do not use the relationship between task periods. In this paper we define initial values using the largest and the second largest periods in a system. We show that the new initial values can significantly improve the exact test.

Many optimal uniprocessor schedulers, such as earliest deadline first (EDF) and rate monotonic (RM), do not have a good schedulability bound on multiprocessor systems. In this paper, we study an on-line algorithm earliest deadline first until Zero laxity (EDZL) for multiprocessor systems. A set of tasks scheduled by EDZL is scheduled using EDF until a job experiences a zero laxity. To avoid the job from missing its deadline, the priority of the job is immediately promoted to the highest priority. We derive the schedulability bound of 3/2+\umax-1/2\ for two-processor systems, where umaxis the maximum utilization of an individual task in the given task set. We also discuss the best known upper bound and lower bound on EDZL schedulability conditions.

Newly popular Internet applications such as WebTV and Internet streaming requires network to support end-to-end delay bound. In this paper, we propose a novel network scheduling scheme, called the bulk scheduling scheme (BSS), built on top of existing schedulers of intermediate nodes (routers) without modifying transmission protocols on both sender and receiver. By inserting TED packets into packet flows at the ingress router periodically, the BSS schedulers of the intermediate nodes can dynamically allocate the necessary bandwidth to each flow to enforce the end-to-end delay. The introduction of TED packets incurs a lower overhead than the per-packet marking approaches, while achieves similar performance. Three flow bandwidth estimation methods are presented and a dropping policy is introduced to discard late packets. We also propose a feedback mechanism to discover and resolve the bottlenecks for the BSS. The simulation results show that BSS performs efficiently as expected.

Real-time disk scheduling is an important research topic for time-critical multimedia applications. Some well-known research results, such as SCAN-earliest deadline first (EDF) and DM-SCAN, applied the SCAN scheme to reschedule service sequence of input tasks and reduce their service time. In this paper, we prove that the general disk-scheduling problem with linear cost-function is NP hard. We also propose the shortest-task-first-DM, a new real-time disk-scheduling algorithm using the concept of the shortest-task-first and the deadline modification. As shown in the experimental results, our approach can schedule more tasks to meet their deadlines.

Data broadcast is an efficient information delivery model that can deliver information to a large population simultaneously. In this paper, we propose two efficient algorithms to broadcast real-time and non-real-time data together. The goal of our algorithms is to reduce the average response time of non-real-time data under the constraint that all real-time data must meet their deadlines. The experimental results show that our proposed algorithms can reduce the average response time while guaranteeing the timing constraints.

To offer a more efficient wireless data access service than 2G/2.5G/3G networks, public WLAN (PWLAN) stands in a predominant position to embrace the wireless broadband era. Reusing existing mechanisms for user authentication, access control, billing and roaming handling procedures in the mobile territory to construct a complementary network, PWLAN attracts the attention of cellular operators. We investigate a practical end-to-end PWLAN architecture capable of using 2G/3G SIM-based authentication for current mobile users and of simultaneously carrying out Web-based authentication for ordinary users without SIMs (subscriber identity modules). Additionally, we give consideration to confederating various wireless Internet service providers (WISPs) by the RADIUS based roaming mechanism and leverage the existing cellular resource. The proposed considerations and guidelines provide a baseline skeleton for building an extendable and flexible cellular/PWLAN architecture.

A blog (shortened from 'weblog') is a trendy way to share personal journal with others in the cyber world. Traditionally rendering and accessing blogs are normally conducted at a stationary PC. However, such a scheme hinders blog users from writing and reading blogs timely. A short-lived idea came out and passed away suddenly. To facilitate the instant blog updating and retrieving, we combined cellular messaging (SMS/MMS messaging and MMS/WAP push) and open sources (Blosxom and Apache) to develop a novel system for the blog rendering and accessing instantly (BRAINS). BRAINS enables blog users to note down their whims and share interests anytime and anywhere. Blog journalists can utilize their mobile phones in hand to compose and deliver blogs to BRAINS by SMS and MMS messaging at their pleasure. Through p re-registering on BRAINS, readers also can get the up-to-date blogs or notification immediately by MMS push or WAP push respectively. With pervasive networks, BRAINS makes mobile blog rendering and accessing more evident.

Previous real-time disk scheduling algorithms assume that each disk request incurs a physical disk mechanical operation and only consider how to move the disk head under real-time constraints. However, with the increased capacity of on-disk cache, modern disk drives read-ahead data aggressively. Thus, the on-disk cache may service many disk requests without incurring physical disk access. By exploring the design methodology of on-disk cache, in this paper, we propose cache-aware real-time disk scheduling algorithms that take the on-disk cache into consideration during scheduling. Therefore, the scheduling algorithm can help the cache replacement scheme to minimize the cache miss ratio. Besides, the service timing estimation is more accurate in schedulability analysis since the cache effect is considered during scheduling. A simulation-based evaluation shows the proposed scheduling algorithms to be highly successful as compared with the classical real-time disk scheduling algorithms. For example, under sequential workload with 10 sequential streams, the data throughput of our scheme is 1.1 times that of DM-SCAN.

Although extracting information from tables is essential for Internet information agents, most tables are designed for human eyes and their layout and semantic meanings are not well defined. In practice, encoding the layout of each information source is impossible. This work presents a novel semantic search approach capable of extracting information from general tables. Semantic ontology allows our agents to read tables in the same knowledge domain with different layouts. In addition, a system of layout syntax and a set of transformation rules are defined to transform tables into databases without losing their semantic meanings.

In a multimedia system, disk I/O subsystem is the most important component due to its relatively limited throughput and large delay. Previously, by applying SCAN to reschedule tasks having the same deadline, SCAN-EDF tries to improve disk throughput while real time constraints can be satisfied. In DM-SCAN, groups of tasks that can be successfully rescheduled by SCAN under specified real time requirements are identified. They are called MSGs (maximum-scannable-groups). An enlarged-MSG (E-MSG) is proposed to further expand the MSG concept and thus to obtain more improvement in disk throughput. By removing some excess constraints on MSG, E-MSG merges several MSGs as a new scannable group. Experimental results show that the E-MSG scheme is better than both SCAN-EDF and MSG in the disk throughput obtained.

Real-time disk scheduling is one of the most important problems in designing a multimedia system. It has been proved to be NP-complete. Recently, various approaches have been proposed to improve disk throughput under guaranteed real-time requirements. SCAN-EDF, which scans the disk surface to retrieve the task data block under the disk head in order to re-schedule tasks in a real-time EDF (earliest deadline first) schedule, is one of the best-known real-time disk scheduling methods. Since tasks rescheduled in SCAN-EDF should have the same deadline, its efficiency depends on the number of tasks with the same deadline. If all tasks have different deadlines, the scheduling results of SCAN-EDF would be the same as EDF. In this paper, we improve SCAN-EDF by applying different hybrid local-merging and global-inserting schemes. As opposed to SCAN-EDF, in our method tasks rescheduled by SCAN may have different deadlines. Its efficiency is not limited by the number of tasks that have the same deadlines. Experiments show that the proposed method is significantly better than SCAN-EDF. In terms of disk throughput, the improvement obtained is 24% greater than the best-known SCAN-EDF method.

Scheduling tasks with different weights in the imprecise computation model is rather difficult. Each task in the imprecise computation model is logically decomposed into a mandatory subtask and an optional subtask. The mandatory subtask must be completely executed before a deadline to produce an acceptable result; the optional subtask begins after the mandatory subtask to refine the result. The error in the results of a task is measured by the processing time of the unexecuted portion of the optional subtask. This paper proposes a fast algorithm for scheduling imprecise computation with timing constraints on uniprocessor systems. The proposed algorithm can obtain the optimal schedule for different weighted tasks with time complexity O(n log/sup 2/n).

Gang scheduling has been shown to be an effective job scheduling policy for parallel computers that combines elements of space sharing and time sharing. We propose new policies to enable gang scheduling to adapt to environments with real-time constraints. Our work, to our best knowledge, is the first work to attempt to address the real-time aspects of gang scheduling. Our system guided by a metric, called "task utilization workload", can schedule both real-time and non-real-time tasks at the same time. We report simulation results with a family of scheduling algorithms based on our proposed metric. Our scheme is designed to be a practical scheme to be used for large scale industrial and commercial parallel systems. Preliminary simulation results also show that our proposed policy is an effective scheme to perform real-time scheduling, while scheduling non-real-time jobs with fairness and good throughput.

Real-time disk scheduling is important to multimedia systems support for digital audio and video. In these years, various approaches are presented to use the seek-optimizing scheme to improve the disk throughput of a real-time guaranteed schedule. However, as these conventional approaches apply SCAN only to the requests with the same deadline or within the same constant-sized group, their improvements are limited. In this paper, we introduce the DM-SCAN (deadline-modification-SCAN) algorithm with an idea of MSG (maximum-scannable-group). The proposed DM-SCAN method can apply SCAN to MSG iteratively by modifying request deadlines. We have implemented the DM-SCAN algorithm on UnixWare 2.01. Experiments show that DM-SCAN is significantly better than that of the best-known SCAN-EDF method in both the obtained disk throughput and the number of supported disk requests.

In this paper, an efficient parallel algorithm is proposed for finding a k-tree core of a tree network. The proposed algorithm performs on the EREW PRAM in O(log n log* n) time using O(n) work.

This paper describes three algorithms for scheduling preemptive, imprecise tasks on a processor to minimize the total error. Each imprecise task consists of a mandatory task followed by an optional task. Some of the tasks are on-line; they arrive after the processor begins execution. The algorithms assume that when each new on-line task arrives, its mandatory task and the portions of all the mandatory tasks yet to be completed at the time can be feasibly scheduled to complete by their deadlines. The algorithms produce for such tasks feasible schedules whose total errors are as small as possible. The three algorithms are designed for three types of task systems: (1) when every task is on-line and is ready upon its arrival, (2) when every on-line task is ready upon arrival but there are also off-line tasks with arbitrary ready times, and (3) when on-line tasks have arbitrary ready times. Their running times are $O(n\log n)$, $O(n\log n)$, and $O(n\log ^2 n)$, respectively.

We consider the problem of scheduling tasks in the imprecise computation model to minimize the maximum error. Given a task system and a schedule of it, the maximum error of the task system is equal to the error of the task that has the largest error when the task system is executed according to the schedule. We describe two preemptive algorithms for scheduling on a processor n dependent tasks with rational ready times, deadlines, and processing times. Each schedule found by our algorithms is an optimal schedule with the minimum total error, and according to this schedule the maximum error is minimized. The run times of our algorithms are O(n/sup 3/) and O(n/sup 2/).>

The imprecise computation technique has been proposed as a way to handle transient overload and to enhance fault tolerance of real-time systems. In a system based on this technique, each time-critical task is designed in such a way that it can produce a usable, approximate result in time whenever a failure or overload prevents it from producing the desired, precise result. This paper describes ways to implement imprecise computations, models to characterize them and algorithms for scheduling them. An imprecise mechanism for the generation and use of approximate results can be integrated in a natural way with a traditional fault-tolerance mechanism. An architectural framework for this integration is described.>

PERTS is a prototyping environment for real-time systems. It contains schedulers and resource access protocols for time-critical applications, together with a comprehensive set of tools for the analysis, validation, and evaluation of real-time systems built on the scheduling paradigms supported by these building blocks. This paper describes the underlying models of real-time systems supported by PERTS, as well as its capabilities and intended use. A key component is the schedulability analyzer. The basic version of this system of tools supports the validation and evaluation of real-time systems built on the framework of the periodic-task model. This system of tools is now available.>

The deadline of a request is the time instant at which its execution must complete. The deadline of the request in any period of a job with deferred deadline is some time instant after the end of the period. The authors describe a semi-static priority-driven algorithm for scheduling periodic jobs with deferred deadlines: each job is assigned two priorities, the higher one for old requests and the lower one for the current request. This algorithm is called the modified rate-monotonic algorithm and is based on the well-known rate-monotonic algorithm. It is shown that the modified rate-monotonic algorithm is optimal when the deadline of every job is deferred by max (1, gamma -1) periods or more, where gamma is the ratio between the longest period and the shortest period. When the deadline of each job is deferred by one period of the job, any set of n independent jobs whose total utilization is equal to or less than (1+n(2/sup 1/n/-1))/2 can be feasibly scheduled by this algorithm. This bound approaches 0.845 when n approaches infinity.>

Three algorithms for scheduling preemptive, imprecise tasks on a processor to minimize the total error are described. Each imprecise task consists of a mandatory task followed by an optional task. Some of the tasks are online; they arrive after the processor begins execution. The algorithms assume that when each new online task arrives, its mandatory task and the portions of all the mandatory tasks yet to be completed at the time can be feasibly scheduled to be computed by their deadlines. The algorithms produce for such tasks feasible schedules whose total errors are as small as possible. The three algorithms are designed for three types of task systems: (1) when every task is online and is ready upon its arrival; (2) when every task is online and is ready upon arrival but there are also offline tasks with arbitrary ready times; and (3) when online tasks have arbitrary ready times. Their running times are O(n log n), O(n log n), and O(n log/sup 2/ n), respectively.>

A circular arc family F is a collection of arcs on a circle. A circular-arc graph is the intersection graph of an arc family. A Hamiltonian cycle (HC) in a graph is a cycle that passes through every vertex exactly once. This paper presents an $O(n^2 \log n)$ algorithm to determine whether a given circular-arc graph contains an HC. This algorithm is based on two subroutines for interval graphs: (i) a linear time greedy algorithm for the node disjoint path cover problem and (ii) a linear time HC algorithm. If the given graph does not contain an HC, this paper can produce a proof either through the deletion of an appropriate cutset or through the failure to obtain a specific type of HC.

Here the problem of scheduling tasks, each of which is logically decomposed into a mandatory subtask and an optional subtask, is considered. The mandatory subtask must be executed to completion in order to produce an acceptable result. The optional subtask begins after the mandatory subtask is completed and refines the result in order to reduce the error in the result. The optional subtask can be left incomplete. The error in the result of a task is equal to the processing time of the unfinished portion of the optional subtask. Two preemptive algorithms for scheduling, on a uniprocessor system, n dependent tasks with rational ready times, deadlines, and processing times are described. An algorithm is optimal in the following sense: whenever feasible schedules that meet the ready time and deadline constraints of all tasks exist, it finds one that has the minimum total error of all tasks. One of the algorithms is optimal when the tasks have identical weights, and its time complexity is $O(n\log n)$. The other algorithm has time complexity $O(n^2 )$, but is optimal when tasks have different weights. A schedule is said to satisfy the $0/1$ constraint when every optional subtask is either completed or discarded. The problem of finding an optimal feasible schedule that satisfies the $0/1$ constraints and minimizes the total processing time of the discarded optional subtasks is NP-complete. Two algorithms for finding optimal schedules of dependent tasks on a uniprocessor system for the special case when all optional subtasks have identical processing times are presented.

The real-weight maximum cut of a planar graph is considered. Given an undirected planar graph with real-value weights associated with its edges, the problem is to find a partition of the vertices into two nonempty sets such that the sum of the weights of the edges connecting the two sets is maximum. The conventional maximum cut and minimum cut problems assume nonnegative edge weights, and thus are special cases of the real-weight maximum cut. An O(n/sup 3/2/ log n) algorithm for finding a real-weight maximum cut of a planar graph where n is the number of vertices in the graph is developed. The best maximum cut algorithm previously known for planar graphs has running time of O(n/sup 3/).>

Consideration is given to the problem of scheduling tasks each of which is logically decomposed into a mandatory subtask and an optional subtask. The mandatory subtask must be executed to completion. If the available processor time is insufficient, the optional subtask can be left incomplete. The error in the result of a task is equal to the processing time of the unfinished portion of the optional subtask. A description is given of a preemptive algorithm for scheduling n dependent tasks with rational ready times, deadlines, and processing times on a uniprocessor system. This algorithm determines whether feasible schedules that meet the timing constraints of all tasks exist; when feasible schedules exist, it finds one that has the minimum total error. The complexity of this algorithm is O(n log n). A schedule is said to satisfy the 0/1 constraint when every optional subtask is either completed or discarded. The problem of finding an optimal feasible schedule that satisfies the 0/1 constraint and minimizes the number of discarded optional subtasks is NP-complete. Two algorithms are presented for finding optimal schedules of dependent tasks on a uniprocessor system for the special case when all optional subtasks have identical processing times.>