The rapid growth of unstructured data has driven the widespread adoption of LSM-tree-based key-value stores (KV stores). The write amplification resulting from compaction in LSM-trees causes a performance bottleneck. Existing solutions attempt to address this issue through key-value separation strategies. However, these studies fail to optimize the memory components of LSM-trees or provide efficient garbage collection (GC) strategies that achieve high performance while minimizing CPU overhead. These limitations motivate us to propose a GPGPU-empowered gradient data hierarchy and key-value separation for optimizing KV stores, named GDH+ . We utilize GPGPU acceleration for sorting and flushing operations, optimizing the memory components of the LSM-tree. Additionally, we enhance read performance with an LRU-based memory component that distinguishes between hot and cold data, in combination with an adaptive migration strategy. Furthermore, we propose an in-place GC strategy to reduce CPU overhead while maintaining high performance. GDH+ achieves a 2×, 1.5×, and 40% improvement in write performance, read performance, and CPU utilization, respectively, compared to state-of-the-art KV stores.

In NAND flash-based solid-state drives (SSDs), system performance and quality of service tend to be degraded by frequent conflicts between garbage collection (GC) I/Os and user I/Os. To address this challenge, we propose an adaptive workload burst-Aware Garbage Collection (AGC) mechanism to build highperformance SSDs. AGC minimizes conflicts between user I/Os and GC I/Os by jointly considering access patterns in workloads, internal GC, and allocation strategies. The running time of a workload is divided into multiple five-millisecond time windows. AGC incorporates a burst I/O access pattern prediction mechanism, which anticipates I/Os patterns in subsequent time windows according to historical access patterns. Pattern predictions allow AGC to proactively buffer valid pages during GC to prevent interference with forthcoming user I/O requests. According to the status of the underlying flash memory, we implement a hybrid allocation strategy to reduce GC-induced user writes blocking while preserving read parallelism performance. AGC classifies data into four hotness levels (hot, warm, cool, and cold) according to the update interval of the same request. Then, we design a hotness-aware victim block selection policy that prioritizes hot blocks to avert valid data migration during GC, thereby reducing write amplification in SSDs. We evaluate AGC through extensive experiments driven by real-world traces. The findings confirm that compared with state-of-the-art schemes (Baseline, CachedGC, FFT-GC, HIPA, and RDA), AGC reduces read and write response time by up to 81.57% and 69.66%, respectively, with average reductions of 54.34% and 39.21%. Furthermore, AGC decreases GC counts by up to 24.31% with an average of 12.04%, thereby reducing GC overhead and extending SSD lifetime across diverse workloads.

DRAM-based cache is a practical approach to enhancing the performance of large-capacity SSDs. Due to DRAM’s limited capacity, cache sizes are significantly smaller than the data scale of workloads – and cache replacement schemes determine the cache hit ratio and SSD performance when a cache reaches full capacity. Prior work embarked on leveraging machine learning models (ML) to predict future access patterns in workloads, aiding cache replacement decisions for intelligent cache schemes inside SSDs. Unfortunately, existing ML-based cache schemes often overlook the impacts of data granularity – including page, request, and coarse granularities – of training datasets, model inference time overhead, and computational overhead on SSD performance. To address these challenges, we are motivated to propose an sample-inference-based intelligentcachescheme – eCache. eCache accurately predicts the future reuse distance of each sampled requested pages, which can enhance the accuracy of decision-making for the cache replacement. In particular, we design a parallel framework to curb the time overhead caused by model inference. We advocate for a random-group sampling inference method that utilizes the most accurate model while reducing computational overhead. Moreover, we implement eCache on the state-of-the-art SSD simulator, MQSim, and compare it against alternative cache schemes (i.e., CCache, NCache, LAC, and VS-batch). The experimental results unveil that compared with the other cache schemes, eCache significantly reduces the average response time by up to 79.68% with an average reduction of 44.08%. When compared with the page-granularity-ML-empowered cache schemes, eCache greatly curtails computational overhead by up to 85.23% with an average reduction of 66.00%.

It is challenging to store and process massive unstructured data for key-value storage systems that require high concurrency, high performance, and low latency. Log-Structured Merge (LSM) trees-based Key-value stores or KV stores are widely adopted for enhanced write performance. Existing KV stores are primarily deployed on a CPU-centric architecture, which necessitates moving data to the CPU from memory or storage devices for processing. This is particularly problematic during the compaction process, which involves substantial data movement and rewrite. This tradition consumes bandwidth and computational resources, leading to write amplification and impairing system performance. Near-Data Processing (NDP) devices mitigate this issue by processing data at the storage location, thereby reducing data movement cost. Recognizing that the computational power of a single NDP device is insufficient for the demands of large-scale unstructured data processing, we propose JMStore—a multi-NDP key-value store based on a hash data organization. By offloading computational tasks to multiple NDP devices, JMStore collaboratively optimizes the compaction process to address the data movement issue as well as the mismatch between large-scale in workloads data and computational power on an NDP. We design a key-value store programming model and data organization for a multi-NDP architecture, enabling the system to leverage the hardware efficiency and parallelism of multiple NDP devices to significantly optimize system performance. We also propose a strategy to balance storage and computation resources under a hash layout. Compared to the latest single NDP KV store (PStore) and the multi-NDP KV store (MStore), JMStore demonstrates significant performance improvements under DB_Bench and YCSB-C with read-write mixed workloads: the peak improvements can reach a factor of 10.

LSM-tree-based key-value stores or KV stores are widely deployed in modern cloud storage systems thanks to high data storage efficiency and retrieval capabilities. The compaction process in the LSM-tree, however, results in severe performance bottlenecks, especially in scenarios involving large volumes of data. While key-value separation methods mitigate the performance bottlenecks caused by compaction, the existing methods do not fully address merge-sorting during compaction and expensive garbage collection (GC). We propose gParaKV, a GPGPU-empowered KV store with a KV separation mechanism, leveraging the GPGPU parallel technology to accelerate merge-sorting in compaction and GC. gParaKV embraces unique features like a GPGPU bitmap structure, parallel data marking, and a parallel GC mechanism. These critical components effectively curtail the overhead of merge-sorting and GC operations by virtue of parallel computing. We compare it with state-of-the-art KV stores (e.g., RocksDB, BlobDB, Wisckey, DiffKV, UniKV, and HPDK) under various workloads. The experimental results show that gParaKV can improve the write performance and GC efficiency compared to the existing key-value separation-based KV stores.

Subspace clustering is an effective way to analyze high-dimensional data. The main problems of the conventional subspace clustering techniques are as follows: first, conventional clustering methods can not describe categorical attribute space in more detail; second, most subspace-clustering techniques failure to process dynamic data effectively; finally, lack of effective noise recognition leads to the decline of the efficiency of incremental subspace-clustering analysis. We address the above problems by an incremental subspace-clustering algorithm — called ICE. With attribute subspace constructed by a rough set-based weight computing method, ICE obtains clustering results through initial and incremental clustering stage. Utilizing the original cluster results generated from initial clustering stage, we adopt merging and splitting operation to dynamic adjust cluster-structure in incremental clustering stage. Before achieving the final results, a polymerization-based noise recognition technique is employed to automatically identify noise from sparse clusters without human threshold intervention. We implement ICE on synthetic and real-world datasets. The experimental results reveal that incremental subspace-clustering method can achieves satisfactory performance on extensibility, accuracy and robustness.

Log-Structured Merge tree-based key-value (KV) stores, like LevelDB and RocksDB, are extensively applied in large-scale data storage systems. This design excels in write-intensive environments by converting random writes into sequential append operations. Despite its advantages, KV stores struggle with real-world workloads where most updates in KV pairs are infrequent. The compaction process and hierarchical data organization result in high write and read amplification. To mitigate these issues, we propose HAKV – a hotness-aware zone management approach to optimizing performance of KV stores. HAKV first separates hot KV pairs from cold KV pairs, storing hot KV pairs in dedicated zones within persistent memory (PM), enabling centralized and lightweight compaction. Second, we propose a storage zone structure in PM to achieve space optimization for cold KV pairs. Third, to bolster cache hit ratio in PM, we provide a hierarchical data framework for hot KV pairs – and a recycling strategy for invalid hot KV pairs in a zone to enhance the space utilization of PM for hot KV pairs. Finally, we design a dynamic window-based adaptive adjustment mechanism for zone pool in PM to optimize the space utilization. Thus, HAKV significantly reduces write amplification while boosting overall read and write performance. The experimental results demonstrate that HAKV achieves write amplification reduction by up to 92.3%, 79.2%, 90.2%, 41.1%, 80.6%, and 62.4% compared with LevelDB, RocksDB, NoveLSM, LightKV, Wisckey, and UniKV, respectively, with average reduction rates of 89.6%, 74.4%, 84.9% 32.3%, 63.7%, and 42.5%. Furthermore, HAKV boosts random write performance by up to 54.2×, 51.5×, 44.2×, 4.3×, 3.1×, and 4.3×, respectively—and the average improvement reaches 25.8×, 20.9×, 23.9×, 2.7×, 2.5×, and 3.4×.

The Log-structured merge-tree (LSM-tree), widely adopted in key-value stores (KV stores), is esteemed for its efficient write performance and superb scalability amid large-scale data processing. The compaction process of LSM-trees consumes significant computational resources, thereby becoming a bottleneck for system performance. Traditionally, compaction is handled by CPUs, but CPU processing capacity often falls short of increasing demands with the surge in data volumes. To address this challenge, existing solutions attempt to accelerate compaction using GPGPUs. Due to low GPGPU parallelism and data transfer delay in prior studies, the anticipated performance improvements have not yet been fully realized. In this paper, we bring forth RGKV – a comprehensive optimization approach to overcoming the limitations of current GPGPU-empowered KV stores. RGKV features the GPGPU-adapted contiguous memory allocation and GPGPU-optimized key-value block architecture to furnish high-efficient GPGPU parallel encoding and decoding catering to the needs of KV stores. To enhance the computational efficiency and overall performance of KV stores, RGKV employs a parallel merge-sorting algorithm to maximize the parallel processing capabilities of the GPGPU. Moreover, RGKV incorporates a data transfer module anchored on the GPUDirect storage technology – designed for KV stores – and designs an efficient data structure to substantially curtail data transfer latency between an SSD and a GPGPU, boosting data transfer speed and alleviating CPU load. The experimental results demonstrate that RGKV achieves a remarkable 4$\times$improvement in overall throughput and a 7$\times$improvement in compaction throughput compared to the state-of-the-art KV stores, while also reducing average write latency by 70.6%.

Thanks to high-density flash memory and high parallelism, multitenant solid-state drives (MSSDs) have become a popular high-performance storage device for enhancing cache resource utilization and reducing operational costs within these SSDs. The competition for limited cache resources inside the MSSD among multiple tenants, however, can lead to performance interference among the tenants, and prior studies focused on quality of service (QoS) in MSSDs. An efficient caching scheme is crucial for optimizing SSD performance and lifetime. Existing caching schemes aim to shorten response time by the virtue of improved cache hit rates, which offer limited performance improvement as well as low cache resource efficiency. In this article, we propose an intelligent cache allocation scheme named iCache, which employs a long short-term memory (LSTM) model to capture the I/Os access patterns of workloads and dynamically allocates cache resources inside an MSSD according to maximum benefit point (MBP) and optimal allocation point (OAP). The extensive experimental results demonstrate that iCache reduces response time by up to 87%, 24%, and 20% compared against the existing caching schemes—Shared, Justitia, and MLCache, respectively. The empirical study confirms that the new traits of iCache immensely improve system performance by enhancing the cache efficiency of MSSDs and guaranteeing fairness in performance across varying workloads.

The parallel operation technology plays a pivotal role in enhancing performance of 3-D nand flash-based SSDs. High-parallel distribution of consecutive pages places the pages on different parallel units, thereby improving the parallelism and throughput of read requests. However, the high-parallel distribution generates two problems: 1) aggravating data fragmentation and 2) exacerbating the impact of garbage collection (GC) on latency. Moreover, small reads only require a few parallel units, and thus the high-parallel distribution is redundant for the requests. To address this issue, we propose a read-request driven adaptive allocation scheme called RDA to bolster SSD performance by adaptively adjusting the parallel distribution of consecutive pages. The RDA scheme employs the size of historical read requests to gauge the level of parallelism for write requests with varying sizes. Then, RDA allocates the logical pages of writes to distinct parallel units according to the parallelism of the requests. In doing so, RDA effectively mitigates the performance degradation of SSDs caused by redundant parallel distribution, while preserving the parallelism of read requests. We compare RDA with the three state-of-art schemes Amphibian, SOML, and Preemptive GC in terms of GC-blocked read requests, GC counts, and read response time under eight real-world workloads. The experimental results unveil that compared with the existing schemes, RDA revamps the GC-blocked read requests, GC counts, and read response time by averages of 20.6%, 7.8%, and 15.8%, respectively.

The similarity metric has garnered widespread attention thanks to its potential applications in the fields of data mining, machine learning, and so on. Due to the interference of “distance concentration” caused by “Curse of dimensionality,” however, existing similarity metrics are inadequate in high-dimensional data analysis. In this study, we propose two innovative similarity metrics—Chebyshev Coulomb force and Chebyshev Coulomb resultant force—anchored on Chebyshev p-norms. In the initial phase, we eliminate dependency relationships among attributes by applying a metric matrix—and the theoretical analysis reveals that the Chebyshev p-norms is capable of mitigating the effect of “distance concentration” among high-dimensional data objects. Next, we devise two similarity metrics—Chebyshev Coulomb force and Chebyshev Coulomb resultant force—by adopting the metric matrix and Chebyshev p-norms. Chebyshev Coulomb force and Chebyshev Coulomb resultant force, being effective in characterizing the similarity among data objects, quantify the deviation of data objects from their respective dataset centers. Additionally, the two metrics alleviate the interference of “distance concentration.” Importantly, the discrepancy of data objects in attribute dimensions is captured by Chebyshev Coulomb force vector, rendering the similarity metric interpretable. By utilizing the UCI dataset, the experimental validation demonstrates the superiority of our similarity metrics, confirming their efficacy in mitigating the interference of “distance concentration.” Compared with the existing similarity metric approaches, the AUC index of outlier detection shows an average improvement of 8.18%—and the ARI, NMI, and F_score indices of clustering are revamped by averages 6.56%, 6.87%, and 6.01%, respectively.

Key-value stores (KV stores) anchored on log-structured merge trees (LSM-tree) provide much improved performance under write-intensive workloads but exhibit significant write amplification (WA). The tiering compaction strategy is widely adopted in KV stores to reduce the WA. However, there are three imminent issues in tiering-based KV stores. First, excessive levels in the LSM-tree structure result in high read and write amplification. Second, without key partitioning support, these KV stores increase write tail latency. Relying solely on a hash-based key partitioning scheme is insufficient, as it does not support range queries. Furthermore, a KV store with only a key range-based partitioning scheme overlooks the distribution of keys within the key space. Third, existing KV stores with level optimization can incur high costs. A common approach to reducing the number of LSM-tree levels is to increase the MemTable size. While this reduces the number of levels, it requires more memory, leading to higher costs. Therefore, it is crucial to balance the tradeoff between level optimization and monetary expenses. To address these issues, we propose a tiering-based key-value store, leveraging high-performance hierarchical data management. The key space of our proposed KV store is partitioned into m ultiple partitions based on key ranges, with an LSM- tree in each partition. We refer to this KV store as MTree in this article. MTree reduces the number of levels in the LSM-Tree structure close to one without increasing the monetary cost. In MTree, a hierarchical structure that combines the log and LSM-tree curtails the number of levels in the LSM-tree by accumulating the data in the log without increasing the cost. With the hierarchical structure in place, we devise a long- and short-term key density distribution-aware partitioning scheme for the key range. This scheme dynamically adjusts the size of partitioning, balancing data in the partition and storing most data in large-sized logs. Then, MTree reduces the number of levels in the LSM-tree, thereby optimizing the read/write amplification. The experimental results show that MTree limits the WA to as low as two. MTree enhances the random write throughput of the state-of-the-art KV stores by up to 6.9×.

LSM-tree-based key-value stores or KV stores, with their advantage of sequential writes, are widely deployed as backend storage engines. LSM-trees achieve updates by merging data through compaction operations. During compaction, however, background tasks – read, write, and filter large amounts of data – compete against foreground requests for the system’s computational and I/O resources. Although numerous studies have sought to enhance system performance using high-speed storage along with computational devices, bottlenecks in CPU computation and I/Os still persist. Near-data processing (NDP) emerges as an effective solution to mitigate the bottleneck issues: the computational units of an NDP device not only expand the system’s computational resources but also significantly reduce data movement by internally performing computations. Prior collaborative efforts in the NDP device have adopted a time-aware dynamic scheduling mode. Nonetheless, there still exists a noticeable disparity in processing time between a host and its device. To address this gap, we propose WinDB – a KV store that utilizes a window-driven task allocation approach. WinDB advances task allocation in fine-grained key ranges, ensuring that the data volume of compacted SSTables matches the computing capabilities of both host and device. Apart from device-level parallelism, WinDB embraces thread-level parallelism to enhance the system’s overall performance. The experimental results unfold that WinDB bolsters the throughput by up to 4x that of RocksDB, with a significant reduction in average latency. WinDB is capable of curtailing resource contention, which in turn leads to shortened front-end response time.

NAND Flash-based solid-state drives (SSDs) have gained widespread usage in data storage thanks to their exceptional performance and low power consumption. The computational capability of SSDs has been elevated to tackle complex algorithms. Inside an SSD, a DRAM cache for frequently accessed requests reduces response time and write amplification (WA), thereby improving SSD performance and lifetime. Existing caching schemes, based on temporal locality, overlook its variations, which potentially reduces cache hit rates. Some caching schemes bolster performance via flash-aware techniques but at the expense of the cache hit rate. To address these issues, we propose a random forest machine learning Classifier-empowered Cache scheme named CCache, where I/O requests are classified into critical, intermediate, and non-critical ones according to their access status. After designing a machine learning model to predict these three types of requests, we implement a trie-level linked list to manage the cache placement and replacement. CCache safeguards critical requests for cache service to the greatest extent, while granting the highest priority to evicting request accessed by non-critical requests. CCache – considering chip state when processing non-critical requests – is implemented in an SSD simulator (SSDSim). CCache outperforms the alternative caching schemes, including LRU, CFLRU, LCR, NCache, ML_WP, and CCache_ANN, in terms of response time, WA, erase count, and hit ratio. The performance discrepancy between CCache and the OPT scheme is marginal. For example, CCache reduces the response time of the competitors by up to 41.9% with an average of 16.1%. CCache slashes erase counts by a maximum of 67.4%, with an average of 21.3%. The performance gap between CCache and and OPT is merely 2.0%-3.0%.

Inside an NAND Flash-based solid-state disk (SSD), utilizing DRAM-based write-back caching is a practical approach to bolstering the SSD performance. Existing caching schemes overlook the problem of high user I/Os intensity due to the dramatic increment of I/Os accesses. The hefty I/O intensity causes access conflict of I/O requests inside an SSD: a large number of requests are blocked to impair response time. Conventional passive update caching schemes merely replace pages upon access misses in event of full cache. Tail latency occurs facing a colossal I/O intensity. Active write-back caching schemes utilize idle time among requests coupled with free internal bandwidth to flush dirty data into flash memory in advance, lowering response time. Frequent active write-back operations, however, cause access conflict of requests – a culprit that expands write amplification (WA) and degrades SSD lifetime. We address the above issues by proposing awork Load intensity-aware and Active parallelCachingscheme - LAC - that is powered by collaborative-load awareness. LAC fends off user I/Os’ access conflict under high-I/O-intensity workloads. If the I/O intensity is low – intervals between consecutive I/O requests are large – and the target die is free, LAC actively and concurrently writes dirty data of adjacent addresses back to the die, cultivating clean data generated by the active write-back. Replacing clean data in priority can reduce response time and prevent flash transactions from being blocked. We devise a data protection method to write back cold data based on various criteria in the cache replacement and active write-backs. Thus, LAC reduces WA incurred by actively writing back hot data and extends SSD lifetime. We compare LAC against the six caching schemes (LRU, CFLRU, GCaR-LRU, MQSim, VS-Batch, and Co-Active) in the modern MQSim simulator. The results unveil that LAC trims response time and erase count by up to 78.5% and 47.8%, with an average of 64.4% and 16.6%, respectively.

With high scalability and flexibility, serverless computing is becoming the most promising computing model. Existing serverless computing platforms initiate a container for each function invocation, which leads to a huge waste of computing resources. Our examinations reveal that (i) executing invocations concurrently within a single container can provide comparable performance to that provided by multiple containers (i.e., traditional approaches); (ii) redundant resources generated within a container result in memory resource waste, which prolongs the execution time of function invocations. Motivated by these insightful observations, we propose FaaSBatch - a serverless framework that reduces invocation latency and saves scarce computing resources. In particular, FaaSBatch first classifies concurrent function requests into different function groups according to the invocation information. Next, FaaSBatch batches the invocations of each group, aiming to minimize resource utilization. Then, FaaSBatch utilizes an inline parallel policy to map each group of batched invocations into a single container. Finally, FaaSBatch expands and executes invocations of containers in parallel. To further reduce invocation latency and resource utilization, within each container, FaaSBatch reuses redundant resources created during function execution. We conduct extensive experiments based on Azure traces to evaluate the effectiveness and performance of FaaSBatch. We compare FaaSBatch with three state-of-the-art schedulers Vanilla, SFS, and Kraken. Our experimental results show that FaaSBatch effectively and remarkably slashes invocation latency and resource overhead. For instance, when executing I/O functions, FaaSBatch cuts back the invocation latency of Vanilla, SFS, and Kraken by up to 72.58%, 74.10%, and 72.62%, respectively; FaaSBatch also slashes the resource overhead of Vanilla, SFS, and Kraken by 70.2% to 98.40%, 67.74% to 98.12%, and 43.01% to 78.90%, respectively.

LSM-tree-based key-value stores (KV stores) convert random-write requests to sequence-write ones to achieve high I/O performance. Meanwhile, compaction operations in KV stores update SSTables in forms of reorganizing low-level data components to high-level ones, thereby guaranteeing an orderly data layout in each component. Repeated writes caused by compaction (a.k.a. write amplification) impacts I/O bandwidth and overall system performance. Near-data processing (NDP) is one of the effective approaches to addressing this write-amplification issue. Most NDP-based techniques adopt synchronous parallel schemes to perform a compaction task on both the host and its NDP-enabled device. In synchronous parallel compaction schemes, the execution time of compaction is determined by a subsystem that has lower compaction performance coupled by under-utilized computing resources in a NDP framework. To solve this problem, we propose an asynchronous parallel scheme named PStore to improve the compaction performance in KV stores. In PStore, we designed a multi-tasks queue and three priority-based scheduling methods. PStore elects proper compaction tasks to be offloaded in host- and device-side compaction modules. Our proposed cross-leveled compaction mechanism mitigates write amplification induced by asynchronous compaction. PStore featured with the asynchronous compaction mechanism fully utilizes computing resources in both host- and device-side subsystems. Compared with the two popular synchronous compaction modes based on KV stores (TStore and LevelDB), our PStore immensely improves the throughput by up to a factor of 14 and 10.52 with an average of a factor of 2.09 and 1.73, respectively.

Log-structured-merge tree or LSM-tree is a technological underpinning in key-value (KV) stores to support a wide range of performance-critical applications. By conducting data re-organization in the background by virtue of compaction operations, the KV stores have the potential to swiftly service write requests with sequential batched disk writes and read requests for KV items constantly sorted by the compaction. Compaction demands high I/O bandwidth and CPU speed to facilitate quality service to user read/write requests. With the emergence of high-speed SSDs, CPUs are increasingly becoming a performance bottleneck. To mitigate the bottleneck limiting the KV-store’s performance and that of the applications supported by the store, we propose a system - gLSM - to leverage GPGPU to remarkably accelerate the compaction operations. gLSM fully utilizes the parallelism and computational capability inside GPGPUs to improve the compaction performance. We design a driver framework to parallelize compaction operations handled between a pair of CPU and GPGPU. We employ data independence and GPGPU-orient radix-sorting algorithm to concurrently conduct compaction. A key-value separation method is devised to slash the transfer of data volume from CPU-side memory to the GPGPU counterpart. The results reveal that gLSM improves the throughput and compaction bandwidth by up to a factor of 2.9 and 26.0, respectively, compared with the four state-of-the-art KV stores. gLSM also reduces the write latency by 73.3%. gLSM exhibits a performance improvement by up to 45% compared against its variant where there are no KV separation and collaboration sort modules.

Key-value (KV) stores based on log-structured merge tree (LSM-tree) have been extensively studied and deployed in major information technology infrastructures. Because this type of systems is catered for KV store accessing disks, a limited disk bandwidth increases the difficulty of serving online data requests. One solution involves using a large DRAM such that frequent KV pairs are buffered and accessed from the main memory – and this solution exposes a major design drawback of the KV store: its lack of support for integrated data management in memory and on disks. For example, data in the most popular LSM-tree implementation – RocksDB – may reside in a small write buffer (MemTable) that organizes KV pairs for disk writes, a buffer cache for disk blocks, a write-ahead log on the disk for data persistence, and in various LSM levels on the disk. Without the integrated management of indexes, data, and their persistence in a hierarchical memory/disk architecture, memory is under-utilized along with missed performance optimization opportunities. We propose a KV store, TrieKV, which holistically incorporates DRAM, persistent memory (PMem), and disk with certain desired features: (1) fast in-memory access, (2) accurate identification of hot/cold data at an adaptable granularity, (3) customized memory space allocation for minimized fragmentation, (4) hotness-aware data placement across the storage hierarchy, (5) in-place data persistence in the PMem, and (6) hotness-aware LSM-tree compaction. TrieKV employs a single, integrated trie-structured index for all KV pairs in memory, where access hotness can be consistently discovered. Accordingly, the KV placement is dynamically determined according to the hotness and persistence needs of the storage hierarchy spanning the DRAM, PMem, and solid-state drive. In the experiment, we demonstrate that the 99th latency of RocksDB and NoveLSM is 38x and 6x higher than that of TrieKV, respectively. In addition, TrieKV outperforms RocksDB and NoveLSM by a factor of 5.6 and 1.7in terms of throughput, respectively.

With the rapid growth of cloud computing, frequent workload bursts show an increasing influence on the Quality of Service (QoS) and energy efficiency of cloud-based data centers. Existing virtual machine placement schemes are expected to optimize either QoS or energy efficiency for cloud data centers running under bursty workload conditions. To bridge this gap, we propose a burst-aware and thermal-efficient virtual machine placement technique calledBTVMP. BTVMP adopts a two-step strategy to achieve energy efficiency while assuring QoS. First, BTVMP leverages a split-and-recombine algorithm – SAR – to deal with bursty workloads. SAR prioritizes critical workloads while preventing low-priority workloads from starvation, thereby assuring QoS. Second, BTVMP utilizes an enhanced simulated annealing algorithm calledESAto offer optimal thermal-efficient virtual machine placement (VMP) solutions, aiming to minimize the energy consumption of data centers. To facilitate estimating energy consumption, we integrate into BTVMP a thermal model that takes into account heat re-circulation effects. We conduct extensive experiments with a real-world trace. We compare BTVMP with the leading-edge VMP strategies, including Genetic Algorithm (XINT-GA), Power-Aware and Performance-Guaranteed Virtual Machine Placement (PPVMP), Peak Load Scheduling Control Method (PLSC), First Come First Serve (FCFS), and GReedy based scheduling Algorithm miNImizing Total Energy (GRANITE). The experimental results unveil that BTVMP not only enhances QoS but also exhibits superb energy efficiency. In particular, BTVMP reduces PLSC's workload delay and FCFS's critical workload delay by 18$\%$and 11$\%$, respectively. Moreover, BTVMP lowers the total energy consumption of the three alternative algorithms –GRANITE, XINTGA, PPVMP, and PLSC – by anywhere between 27.8$\%$and 49.4$\%$.

Key-value stores are a key player of managing large-scale unstructured data in storage systems. Performance improvement of the LSM-tree structure has been extensively investigated, but current work primarily focuses on cache structural optimization rather than hot-and-cold data properties. Moreover, existing and external memory components of LSM-tree rarely have uniform hot and cold attributions. In this study, we make use of the gradient and hierarchy mechanism to optimize the components catering for cache data. We design an adaptive data migration method according to hot and cold data in the cache. We reform and expand a gradient cold-hot data hierarchy (GDH) mechanism that replaces the in-memory data structure to address the problem of missing hot and cold data attributes. The hot and cold data are placed in separate cache partitions to store hot data as far the high hierarchy as possible, reducing$\mathrm{I}/\mathrm{O}$accesses. When it comes to frequently accessed hot data, we advocate for a hotness-aware technique for data stored on a disk, where read-write performance and the cache hit rate are revamped. The experiment results reveal that our proposed GDH achieves a high cache-hit ratio and low access latency under a wide range of workloads.

Increasing workload conditions lead to a significant surge in power consumption and computing node failures in data centers. The existing workload distribution strategies focused on either thermal awareness or failure mitigation, overlooking the impact of node failures on the energy efficiency of cloud data centers. To address this issue, a new holistic model is built to characterize the impacts of workloads, computing and cooling costs, heat recirculation, and node failure on the energy efficiency of cloud data centers. Leveraging such a holistic model, we propose a novel thermal-aware workload distribution strategy calledHGSAthat takes node failure into accountand can improve the energy efficiency of cloud data centers. Our empirical findings confirm that (i) faulty nodes lead to a large rise in power consumption, and (ii) failure locations play a vital role in the power consumption of data centers. Experimental results unveil that HGSA is adroit at making near-optimal decisions in workload distribution strategies. In particular, HGSA cuts down the minimum inlet temperature by 5.2$\%$-15$\%$, improves the maximum air temperature of a Computer Room Air Conditioner (CRAC) model by 4.2$\%$-26.5$\%$, lowers the cooling cost by 15.4$\%$-50$\%$compared to the existing solutions. Furthermore, HGSA cuts back the total power consumption by 0.65$\%$-78$\%$.

As cloud platforms become increasingly popular, accurately understanding I/O behaviors in modern cloud storage is of paramount importance for system design and optimization. This paper sheds new light on the correlation of inter-arrival times of both read and write requests at the block level in four representative cloud storage workloads – AliCloud, Systor’17, MSRC and FIU. Our study reveals that I/O arrivals at the block level are very complex in modern cloud storage. There is a certain degree of correlation in the long-term timescale for request arrival intervals in AliCloud and Systor’17_read. Request arrival intervals in MSRC, FIU and Systor’17_write, however, are almost uncorrelated. The Gaussianity test confirms that I/O burstiness appears to be Gaussian in AliCloud_write and Systor’17_read, but the burstiness is non-Gaussian in other workloads. Importantly, we unfold the existence of self-similarity in cloud storage workloads with a certain degree of correlations, via visual evidence, the autocorrelation structure of the aggregated process of I/O request sequences, and Hurst parameter estimates. We further design an alpha-stable workload model for synthetic I/O generation, and the experimental results demonstrate that our model has an edge over conventional models in terms of accurately emulating I/O burstiness.

Multibit 3-D NAND flash-based solid-state disks (SSDs), offering high storage density, contain multiple types of pages to accommodate multiple bits per physical cell. Full sequence program or FSP can program multiple pages in a word line at a time, thereby improving write throughput. Unfortunately, large-grained FSP operations coarsely aggregate consecutive logical pages on the same word line, which adversely affects the parallelism and latency of read requests. Moreover, FSP smooths the program latencies for different types of pages, whereas the pages still exhibit various read latencies. Multiple read latencies and lower read parallelism noticeably deteriorate the completion efficiency of read requests: SSD performance is degraded. To address this issue, we propose an FSP data allocation scheme called FSPDA that incorporates the physical structure characteristics of multibit 3-D NAND, aiming to bolster the read performance of 3-D NAND Flash-based SSDs. FSPDA embraces two distinctive and vital features. First, according to the distance between logical pages, FSPDA allocates logical pages to specified parallel units and stipulates that consecutive logical pages must be assigned to different planes, thus improving read parallelism and data locality. Second, to further reduce read latency, FSPDA employs cache hits to determine hot and cold data to be placed to low-latency and high-latency pages, respectively. We compare FSPDA with two state-of-the-art schemes—OSPADA and single-operation-multiple-location—in terms of multiplane read (MPR) counts, read response time, and GC counts under eight real-world workloads. The experimental results show that compared with the existing schemes, FSPDA slashes the number of MPR counts, read response time, and the number of GC counts by an average of 34.4%, 28.5%, and 13.6%, respectively.

Garbage collection or GC running in the controller of 3-D NAND flash-based solid-state disks—SSDs—plays a critical role in the performance of storage systems. SSD manufacturers have developed various GC solutions based on internal data movement or IDM to mitigate the impacts of GC on request latency. Due to the circuit characteristics of flash memory, the existing IDM-based GC strategies are restricted by page parity during data movement: odd pages must be migrated to odd pages, and even pages to even pages. When migrating two consecutive pages with the same parity, the free page between the two migrated pages will be wasted after the migration is complete. This ever-increasing page waste problem inevitably deteriorates the storage space utilization of flash memory, thereby degrading the overall performance of 3-D NAND flash-based SSDs. To address this issue, we propose a parity-check GC scheme called PcGC to revamp SSD performance by alleviating page waste during GC. We build a parity-check unit in PcGC to facilitate checking the parity of migrated valid pages and destination pages. According to the parity results offered by the parity-check unit, PcGC dynamically adjusts the migration order of valid pages during the course of GC. In doing so, PcGC fundamentally averts page waste caused by the page parity restriction, thereby enhancing 3-D NAND flash performance. We quantitatively evaluate the performance of PcGC in terms of wasted pages, storage utilization, GC counts, write amplification, and average response time. We compare PcGC against the two state-of-the-art schemes—Amphibian and Tiny-tail flash (TTflash). The experimental results derived from the nine real-world workload traces unfold that compared with Amphibian and TTflash: 1) PcGC curtails the number of wasted pages by up to 91.4% with an average of 53.75%; 2) cuts back the number of GC counts by up to 52.2% with an average of 11.9%; and 3) slashes average write response time by up to 77.8% with an average of 13.0%.

Inside a solid-state disk (SSD), cache stores frequently accessed data to shorten the user-I/O response time and reduce the number of read/write operations in flash memory, thereby improving SSD performance and lifetime. Most existing cache schemes anchor in the spatiotemporal locality of I/O requests in workloads. In the face of a long-time workload, high performance and hit rate often get lost in these caching schemes. Flash memory-aware caching schemes trade hit ratio to prolong SSD lifetime. In this article, we advocate for a machine-learning-based caching scheme named NCache to optimize both hit ratio and SSD performance. In NCache, we construct a machine learning (i.e., ML) model to predict whether data are reaccessed before being evicted from the cache. The cache replacement scheme preferentially evicts data that would not be accessed in the cache. The cache space is conserved for valid data that are likely to be repeatedly accessed. A pipelined scheme is implemented to accelerate the ML model, alleviating the time-cost of NCache. A double-linked list boosts the data addressing and cache replacement process. NCache is orthogonal to the existing caching schemes within the flash translation layer. The results validate NCache under a handful of real-world enterprise traces. Taking prn_0 as an example, NCache reduces the response time of LRU, clean first LRU (CFLRU), GCaR_LRU, GCaR_CFLRU, and LCR by up to 15% with an average of 6.4%. The erase count is slashed by 16% at the maximum. Importantly, NCache is adroit at optimizing write amplification by up to 15.9%.

LSM-tree-based key-value stores (KV stores) render high-performance read/write services to data-intensive applications. KV stores employ an SSTable-based Coarse-Grained Compaction (CGC) mechanism, which involves a huge amount of data that do not need to be updated, thereby bringing a high write amplification (WA) and long tail latency. To address this issue, we propose a Fine-Grained Compaction (FGC) mechanism anchored on a Log-Structured patched-Merge tree (LSpM-tree) - a new data organization that averts rewriting irrelevant data into disks amid compaction. A cluster, the basic unit in FGC, encloses several patches and a redirection table, where each patch has an array of KV regions. We devise three compaction modes powered by the LSpM-tree, and we implement a high-performance key-value store, named FGKV. The extensive experiments show that FGKV improves the random-write throughput by up to 121%, 36.8%, 38.6%, and 15.2% compared with LevelDB, RocksDB, LDC, and ALDC, respectively. FGKV lowers the WA of the alternative KV stores by up to 50%. FGKV boosts read performance by up to 122%, 51.4%, 96.6%, and 368%, respectively, and FGKV curbs the 99th percentile latency of LevelDB, RocksDB, LDC, and ALDC by up to 78.2%, 77.6%, 78.3%, and 73.1% under YCSB A, respectively. Moreover, FGKV is readily extended to the other KV stores

Skyline queries have drawn great interest and been widely used in various application domains including multi-criteria decision making, search pruning, and personalized recommendation systems. Given multiple criteria, skyline queries return objects that are not dominated by any other objects. As an extension of traditional skyline queries, probabilistic skyline queries aim to cope with uncertain datasets. This paper presents a novel MapReduce-based framework, ProbSky, in support of fast parallel evaluation of probabilistic skyline queries on large high-dimensional data. ProbSky efficiently evaluates exact p-skyline queries on large uncertain data without compromising the quality of query results. From the theoretical point of view, we formally prove two pruning lemmas integrated with ProbSky to strengthen the early pruning capacity. ProbSky builds on top of three optimization techniques, namely, dominant instance pruning, grid-based partitioning, and pivot point-based acceleration. Extensive experiments on both real and synthetic datasets unveil that compared to the state-of-the-art, ProbSky speeds up the evaluation of exact p-skyline queries on large high-dimensional data by at least one order of magnitude in most cases. Our experimental results also validate that by balancing the memory consumption and execution time among machines, ProbSky is adroit at curbing the bottleneck effect that causes severe system performance deterioration.

Traditional outlier detections are inadequate for high-dimensional data analysis due to the interference of distance tending to be concentrated (“curse of dimensionality”). Inspired by the Coulomb’s law, we propose a new high-dimensional data similarity measure vector, which consists of outlier Coulomb force and outlier Coulomb resultant force. Outlier Coulomb force not only effectively gauges similarity measures among data objects, but also fully reflects differences among dimensions of data objects by vector projection in each dimension. More importantly, Coulomb resultant force can effectively measure deviations of data objects from a data center, making detection results interpretable. We introduce a new neighborhood outlier factor, which drives the development of a high-dimensional outlier detection algorithm. In our approach, attribute values with a high deviation degree is treated as interpretable information of outlier data. Finally, we implement and evaluate our algorithm using the UCI and synthetic datasets. Our experimental results show that the algorithm effectively alleviates the interference of “Curse of Dimensionality”. The findings confirm that high-dimensional outlier data originated by the algorithm are interpretable.

Garbage collection (GC) plays a pivotal role in the performance of 3D NAND flash memory, where Copyback has been widely used to accelerate valid page migration during GC. Unfortunately, copyback is constrained by the parity symmetry issue: data read from an odd/even page must be written to an odd/even page. After migrating two odd/even consecutive pages, a free page between the two migrated pages will be wasted. Such wasted pages noticeably lower free space on flash memory and cause extra GCs, thereby degrading solid-state-disk (SSD) performance. To address this problem, we propose a page-state-aware cache scheme called PSA-Cache , which prevents page waste to boost the performance of NAND Flash-based SSDs. To facilitate making write-back scheduling decisions, PSA-Cache regulates write-back priorities for cached pages according to the state of pages in victim blocks. With high write-back-priority pages written back to flash chips, PSA-Cache effectively fends off page waste by breaking odd/even consecutive pages in subsequent garbage collections. We quantitatively evaluate the performance of PSA-Cache in terms of the number of wasted pages, the number of GCs, and response time. We compare PSA-Cache with two state-of-the-art schemes, GCaR and TTflash, in addition to a baseline scheme LRU. The experimental results unveil that PSA-Cache outperforms the existing schemes. In particular, PSA-Cache curtails the number of wasted pages of GCaR and TTflash by 25.7% and 62.1%, respectively. PSA-Cache immensely cuts back the number of GC counts by up to 78.7% with an average of 49.6%. Furthermore, PSA-Cache slashes the average write response time by up to 85.4% with an average of 30.05%.

Serverless computing is a leading force behind deploying and managing software in cloud computing. One inherent challenge in serverless computing is the increased overall latency due to duplicate computations. Our initial investigation into the function invocations of serverless applications reveals an abundance of duplicate invocations. Inspired by this critical observation, we introduceHashCache, a system designed to cache duplicate function invocations, thereby mitigating duplicate computations. In HashCache, serverless functions are classified into three categories, namely, computational functions, stateful functions, and environment-related functions. On the grounds of such a function classification, HashCache associates the stateful functions and their states to build an adaptive synchronization mechanism. With this support, HashCache exploits the cached results of computational and stateful functions to serve upcoming invocation requests to the same functions, thereby reducing duplicate computations. Moreover, HashCache stores remote files probed by stateful functions into a local cache layer, which further curtails invocation latency. We implement HashCache within theApache OpenWhiskto forge a cache-enabled serverless computing platform. We conduct extensive experiments to quantitatively evaluate the performance of HashCache in terms of invocation latency and resource utilization. We compare HashCache against two state-of-the-art approaches -FaaSCacheandOpenWhisk. The experimental results unveil that our HashCache remarkably reduces invocation latency and resource overhead. More specifically, HashCache curbs the 99-tail latency of FaaSCache and OpenWhisk by up to 91.37% and 95.96% in real-world serverless applications. HashCache also slashes the resource utilization of FaaSCache and OpenWhisk by up to 31.62% and 35.51%, respectively.

Depression is one of the leading factors in global disability and a top driver for suicides. Studies have shown that depression has an effect on language usage. In recent years, especially during the COVID pandemic, social media platforms have become the de facto platform for many individuals to self-disclose or discuss mental health issues like depression. This trend presents a unique opportunity for researchers and healthcare professionals to detect potential mental illnesses for early intervention or treatment by taking advantage of the recent advances in machine learning approaches. Existing depression detection methods on social media, however, suffer from two major limitations. First, these solutions heavily rely on the amount, quality, and type of user-posted content. Second, the overlooked social circle impact should be leveraged to enhance the prediction capabilities. In this paper, we propose a depression detection framework, MentalNet, based on heterogeneous graph convolution by capturing users’ interactions (replies, mentions, and quotetiveets) with their friends on social media and differentiating the intimacy of users’ social circles (e.g., family, friends, or acquaintances). Specifically, we formulate the problem of depression detection on social media as a graph classification problem by representing users’ social circles in the format of heterogeneous graphs. MentalNet embraces three modules, (1) extraction of ego-network node features, (2) construction of user interaction graphs, and (3) depression detection based on heterogeneous graph classification. The extensive experiments on Twitter data demonstrate that MentalNet consistently and significantly outperforms the state-of-the-art methods in terms of all the effectiveness metrics. Compared to the baseline methods, MentalNet is able to effectively predict early depression in Twitter users with up to 24% improvement on F1 score.

Erasure-coded archival converts the redundancy mechanism of low access-frequency data from replication to erasure coding for balancing access performance and storage efficiency. A variety of pipelined schemes are designed to speed up the archival operation, however they neglect such three factors as heterogeneous network, under-utilization of replica resources and tight coupling with underlying platforms which restrict or even negate the performance gains. In this paper, we propose Archpipe, a fast and flexible pipelined erasure-coded archival scheme. It exhibits three distinct features: 1) heterogeneous network awareness, for a single-pipelined construction, sufficient-bandwidth links are given high scheduling priority to avoid network congestion, while considering locality to reducing network transmissions; 2) parallel encoding, the unused replica resources are exploited to adaptively construct multiple pipelines for each stripe based on the single-pipelined algorithm, thereby enabling parity blocks to be encoded in parallel; 3) loose coupling, it does not rely on specific block placement policies and stripe construction algorithms. Experimental results indicate that, Archpipe can be seamlessly integrated with common distributed storage systems, and it improves the erasure-coded archival performance by 3.6 ∼ 4.7× and 1.3 ∼ 2.6× in on-disk and in-memory scenarios, respectively.

Power Management Strategies and the impact of carbon dioxide emission from the data centers across the globe have drawn significant attention worldwide. The rapid growth of energy consumed in data centers has lead to 1) huge costs 2) depletion of non-renewable resources such as coal and petroleum, and 3) emission of greenhouse gases like CO2 in the atmosphere. These greenhouse gas significantly contributes to the climate change of the earth. To tackle this challenge, our research deals with modeling the energy resources of data centers, thereby offering insights to reduce global carbon footprint and energy cost. In our model, we prioritize green energy consumption by eliminating the brown energy resources. In this process, we devise an algorithm that can determine the amount of CO2 emission in the atmosphere per hour by different energy resources. We create an energy model for data centers by incorporating the support vector regression algorithm. Our model is adroit at projecting energy consumed in data centers powered by green energy. Our experimental results confirm that our model consistently delivers high prediction accuracy in terms of energy usage in data centers. The model is expected to facilitate data analytic venues to optimize energy efficiency and sustainability for the development of future data centers.

Leveraging on-site renewable sources like solar and wind provides ample opportunities on developing environmental friendly and energy-efficient data centers. Evidence shows that renewable-aware job schedulers conserve energy by adjusting the arrangement of non-urgent workload according to renewable energy states. We propose an energy management system with a renewable-aware scheduler called REDUX3, which offers a smart way of managing the energy supply of data centers powered by the grid and renewable energy. Due to the intermittent nature of renewable energy resources, REDUX3 judiciously back-fills workload when renewable energy is sufficient, and defer workload to the next time slot if renewable energy is at outage state. As an integrated and smarter update from our previous work [1], [2] and [3], REDUX3 also orchestrates distribute UPS devices (i.e., recharge or discharge) to allocate energy resources when (1) grid price is at low or high states or (2) renewable energy generation is at a low or fluctuating level. Compared with the existing strategies, REDUX3 demonstrates a prominent capacity of boosting renewable energy utilization.

Fake news is a rampant societal and organizational problem with various social media outlets further aggravating its spread. There is a pressing demand to assist people to identify misinformation from massive amount of news data in a timely manner. Detecting Fake news in a timely manner is critical for mitigating its impact. In this research, we propose a novel approach for detecting fake news in real time, RT-FEND (Real Time- FakE News Detection), which relies on distributed computing paradigm. The proposed methodology utilizes event and topic extraction techniques along with a topic- merging mechanism to process real time news data and reduce the number of topics for managing the curse of dimensionality. We report the findings from several experiments to compare RT-FEND with other systems to benchmark in different system settings. RT-FEND approach is more performance-improved and time-efficient in detecting fake news when compared to other fake news detection baselines.

Abstract Models for virtual machines running on cloud computing systems. Modeling system behaviors of clouds is a grand challenge because the resource utilization in VMs is heterogeneous due to variability in workload conditions. We address this challenging issue by uniquely (1) objectifying the usage prediction of virtualized resources and (2) predicting the performance trends of programs running on clouds. At the heart of the modeling system, we pay particular attention to CPU cores, disk size, main memory space, and input data volume, which serve as important factors for the developed prediction module. We devise two resource‐utilization prediction algorithms driven by two distinctive sets of I/O and CPU intensive benchmarks, where one algorithm deals with execution time and the other one revolves around input data size. We investigate the correlation between CPU/disk utilization and VM live migrations. Our system aims at not only providing performance optimization for virtualized resources but also ensuring service level agreement (SLA) and Quality of Service (QoS). The model fits the curve quite well, thereby advocating for the efficiency of the algorithm. The case studies conducted in this project draw the comparisons between the performance of striped and monolithic disks as well as bringing forth the problem of cache coherence that causes hindrance to the experiment. We also deal with the cache‐coherence problem to improve the accuracy of our prediction algorithms

While depression is rated as the most important leading factor to global disability, early detection of depression is a non-trivial task. Existing depression detection mechanisms harvesting social media data suffer from two major limitations. First, existing solutions rely heavily on the amount, quality, and variety of content types (textual, visual, etc.) posted by users to make accurate inferences, therefore suffering from the cold-start problem when coping with users with limited training data (e.g., most existing works exclude users with fewer than 25 tweets). Second, existing approaches ignore the social impact or indication from users' social circles that can be leveraged to enhance the inference results. In this paper, we present MentalSpot, a social-contagion based depression early-screening framework using meta-learning. Specifically, we first construct a social-contagion driven data repository PsycheNet, filling the void of social-circle based depression datasets. We design a triplet network to extract users' embeddings based on the similarities of the linguistic features extracted from written texts. Afterwards, for each target user, we employ dynamic mean shift pruning to select her top-k homogeneous friends in the metric space, the texts written by whom will then be leveraged to train a friend based depression detection model. Extensive experiments show that MentalSpot outperforms the state of the art in terms of all effectiveness metrics, especially for users with very few tweets. Specifically, by using only five tweets per user, MentalSpot successfully yields an F1 score that would otherwise be achieved by the state-of-the-art methods requiring at least twenty tweets. Our approach represents a step forward to address the cold-start problem that deep learning techniques struggle with for their applications in psychiatric diagnosis. The principal beneficiaries of this study are healthcare professionals in medical institutions to determine timely and targeted interventions in a clinical setting. This study also supports non-profit groups in reaching out to people with mental health issues, helping in a global health task that cannot be fully covered by clinicians.

As one of the specific vision tasks, person re-identification has become a prevalent research topic in the field of multimedia and computer vision. However, existing feature extraction methods, originating from the quality of the bounding boxes which could cause the inhomogeneity and incoherence of person representation for cluttered backgrounds, are difficult to adapt the challenges of the harsh real-world scenarios. This study develops a Triplet person Appearances Parsing Framework (TAPF) which eliminates the surrounding interference factors of bounding boxes for person re-identification. The framework consists of a triplet person parsing network and an integration mechanism for person local and global appearance information. Concretely, the triplet parsing network includes a channel parsing module, a position parsing module and a color parsing module, which are used to extract the person channel parsing descriptor, regional descriptor and color perception descriptor, respectively. Then, a local and global flatten gaussian operations are performed to integrate the person appearance parsing descriptors to obtain more discriminative features for the person representation. The experimental results have been conducted to validate our proposed algorithm can achieve a better performance for person re-identification on several public datasets, i.e., VIPeR and Market-1501, respectively.

To satisfy high reliability accompanied by space efficiency requirements, erasure coding is elected to substitute replication as a redundancy mechanism of in-memory clusters. More often than not, the use of erasure coding is limited to read-intensive applications, in which data in erasure-coded clusters are rarely updated. The essential rationale is that update penalty incurred by parity-synchronizations makes long write latency compared with read latency counterpart.In this paper, we propose F-Write: a fast RDMA-supported write optimization scheme for erasure-coded in-memory clusters. It entails two distinct features: 1) an extended version of consistency protocol called Fast2PC is created. It directly modifies remote memory regions using one-sided WRITE verb provided by RDMA to implement the operations of transaction log, and records multiple transactions in the log to submit together, effectively curtailing network latency; 2) a speculative update approach is given to substitute immediate update. Aggregated undo transactions are handled speculatively to synchronize parity blocks in the background when parity blocks are needed. For multiple writes to an identical data block at different times-tamps, only the original and the latest data blocks are involved in calculating parity blocks, thus mitigating encoding latency. Experimental results indicate that F-Write has lower latency, higher throughput compared to the candidate write schemes. Moreover, the impact on recovery time is negligible. Specifically, under the update-intensive workloads, F-Write cuts down write latency by more than 61%, thereby boosting system throughput by a factor of at least 2.6x.

In modern cloud computing environments, there is a tremendous growth of data to be stored and managed in data centers. Large-scale data centers demand high utilization of computing and storage resources, which lead to expensive operational cost for energy usage. Evidence shows that consolidating virtual machines (VMs) can conserve energy consumption in clouds through VM migrations. VM-consolidation techniques, however, inevitably induce a burden on performance. To address this issue, we propose a holistic solution - EGRET - to boost energy efficiency of cloud computing platforms by seamlessly integrating the DVFS scheme with the VM-consolidation technique. EGRET dynamically determines the most energy-efficient strategy by issuing a command to either scale CPU frequencies on a VM or marking the VM as underutilized. We conduct extensive experiments to evaluate the performance of EGRET. The experimental results show that EGRET substantially improves the energy efficiency of cloud computing platforms.

With the development and decreasing cost of next-generation sequencing technologies, the study of the human microbiome has become a rapid expanding research field, which provides an unprecedented opportunity in various clinical applications such as drug response predictions and disease diagnosis. It is thus essential and desirable to build a prediction model for clinical outcomes based on microbiome data that usually consist of taxon abundance and a phylogenetic tree. Importantly, all microbial species are not uniformly distributed in the phylogenetic tree but tend to be clustered at different phylogenetic depths. Therefore, the phylogenetic tree represents a unique correlation structure of microbiome, which can be an important prior to improve the prediction performance. However, prediction methods that consider the phylogenetic tree in an efficient and rigorous way are under-developed. Here, we develop a novel deep learning prediction method MDeep (microbiome-based deep learning method) to predict both continuous and binary outcomes. Conceptually, MDeep designs convolutional layers to mimic taxonomic ranks with multiple convolutional filters on each convolutional layer to capture the phylogenetic correlation among microbial species in a local receptive field and maintain the correlation structure across different convolutional layers via feature mapping. Taken together, the convolutional layers with its built-in convolutional filters capture microbial signals at different taxonomic levels while encouraging local smoothing and preserving local connectivity induced by the phylogenetic tree. We use both simulation studies and real data applications to demonstrate that MDeep outperforms competing methods in both regression and binary classifications. Availability and Implementation: MDeep software is available at https://github.com/lichen-lab/MDeep Contact:[email protected].

Understanding the functional consequence of noncoding variants is of great interest. Though genome-wide association studies or quantitative trait locus analyses have identified variants associated with traits or molecular phenotypes, most of them are located in the noncoding regions, making the identification of causal variants a particular challenge. Existing computational approaches developed for prioritizing noncoding variants produce inconsistent and even conflicting results. To address these challenges, we propose a novel statistical learning framework, which directly integrates the precomputed functional scores from representative scoring methods. It will maximize the usage of integrated methods by automatically learning the relative contribution of each method and produce an ensemble score as the final prediction. The framework consists of two modes. The first 'context-free' mode is trained using curated causal regulatory variants from a wide range of context and is applicable to predict regulatory variants of unknown and diverse context. The second 'context-dependent' mode further improves the prediction when the training and testing variants are from the same context. By evaluating the framework via both simulation and empirical studies, we demonstrate that it outperforms integrated scoring methods and the ensemble score successfully prioritizes experimentally validated regulatory variants in multiple risk loci.

Combining the Internet-of-Things (IoT) technology with cloud computing is a significant alternative for powering the utilization of computing resources in a connected environment. A grand challenge in communications is raised by the emergence of big data, due to the large-sized data transmissions and frequent data exchanges. Applying fog computing is considered an option for resolving the communication challenge. However, a high extent of available heterogeneous computing attached to fog computing servers leads to a restriction of the resource management. This Article addresses the resource management issue by proposing a novel approach - named Energy-aware Fog Resource Optimization (EFRO) model- to optimizing the utilization of connected devices in fog computing. We develop a heuristic algorithm minimizing both energy cost and time consumption in a holistic way. A salient feature of EFRO lies in the integration of the standardization and smart shift operations fueled by a hill-climbing mechanism to produce near-optimal resource allocation solutions. Experimental results demonstrate that our EFRO is adroit at making near-optimal decisions in managing resources in fog computing environments. In particular, EFRO boosts the energy efficiency of the existing MESF and RR schemes by 54.83 and 71.28 percent, respectively. EFRO shortens DECM's allocation-generation time by up to a factor of 507.

To build energy-efficient datacenters, one widely used way is to dynamically manipulate the quantity of available hardware resources on demand. However, when bursty workloads appear, additional time overhead is required for resource gearing, thus incurring a performance degradation. To explore this problem, we present an intelligible analysis on the request handing in a VM. From the analysis, we find that, when workloads are overloaded (i.e., peak loads appear), the number of QoS guaranteed requests can be greatly increased by deferring the scheduling of a few requests. Inspired by this finding, we propose a Peak Load Scheduling Control (PLSC) method to promote the Quality of Service (QoS) of peak loads for modern energy-efficient datacenters. However, peak loads are usually difficult to identify. To overcome this difficulty, PLSC tracks the number of requests residing in a VM by leveraging a two-tier request queue maintained by it. When the number exceeds the capability of the VM, it means that peak loads appear. In this case, PLSC adds some delay-tolerant requests to the secondary queue. The scheduling of requests in the secondary queue is controlled with a lower priority than that of requests in the primary queue. Sequentially, with critical requests maintained in the primary queue, PLSC shortens the response time of critical requests. In addition, PLSC expands the number of QoS-guaranteed requests. Comprehensive experiments are conducted to attest the effectiveness of PLSC, by simulating a typical energy-efficient datacenter. The experimental results show that PLSC significantly promotes the QoS of workloads with a negligible impact on energy saving.

With the explosive data growth, an enormous number of computing and networking components (e.g., servers, switches, and wires) are continuously being augmented to data centers. Data center networks (DCNs) - maintaining a high network capacity - must be cost efficient, incrementally scalable, and fault-tolerant. To address these challenges, we propose in this study a new type of DCN architecture referred to asCriso. Different from the existing network architectures,Crisois designed hierarchically and recursively by employing two ports servers and commodity switches.Crisois constructed based on numerous isomorphicpods, each of which leverages external interfaces supplied by switches to connect with neighboring pods. Additionally, apod-based and fault-tolerant routing algorithm is designed to handle multiple failures.Crisohas an array of promising features, including being cost-efficient and delivering a high-network capacity that can be extended to millions of nodes. The analytic results demonstrate thatCrisois significantly superior to the four state-of-the-art data center structures in terms of network capacity, scalability, cost, power consumption, and other static characteristics. Furthermore, the experimental results unveil thatCrisosatisfies the fault-tolerant demands of modern data centers. Compared to the four existing topologies (i.e.,DCell,BCube,FiConn,Fat-Tree) that have been widely investigated,Crisois adroit at maintaining a balanced performance in terms of throughput and latency.

Data deduplication techniques construct an index consisting of fingerprint entries to identify and eliminate duplicated copies of repeating data. The bottleneck of disk-based index lookup and data fragmentation caused by eliminating duplicated chunks are two challenging issues in data deduplication. Deduplication-based backup systems generally employ containers storing contiguous chunks together with their fingerprints to preserve data locality for alleviating the two issues, which is still inadequate. To address these two issues, we propose a container utilization based hot fingerprint entry distilling strategy to improve the performance of deduplication-based backup systems. We divide the index into three parts: hot fingerprint entries, fragmented fingerprint entries, and useless fingerprint entries. A container with utilization smaller than a given threshold is called a sparse container . Fingerprint entries that point to non-sparse containers are hot fingerprint entries. For the remaining fingerprint entries, if a fingerprint entry matches any fingerprint of forthcoming backup chunks, it is classified as a fragmented fingerprint entry. Otherwise, it is classified as a useless fingerprint entry. We observe that hot fingerprint entries account for a small part of the index, whereas the remaining fingerprint entries account for the majority of the index. This intriguing observation inspires us to develop a hot fingerprint entry distilling approach named HID . HID segregates useless fingerprint entries from the index to improve memory utilization and bypass disk accesses. In addition, HID separates fragmented fingerprint entries to make a deduplication-based backup system directly rewrite fragmented chunks, thereby alleviating adverse fragmentation. Moreover, HID introduces a feature to treat fragmented chunks as unique chunks. This feature compensates for the shortcoming that a Bloom filter cannot directly identify certain duplicated chunks (i.e., the fragmented chunks). To take full advantage of the preceding feature, we propose an evolved HID strategy called EHID . EHID incorporates a Bloom filter, to which only hot fingerprints are mapped. In doing so, EHID exhibits two salient features: (i) EHID avoids disk accesses to identify unique chunks and the fragmented chunks; (ii) EHID slashes the false positive rate of the integrated Bloom filter. These salient features push EHID into the high-efficiency mode. Our experimental results show our approach reduces the average memory overhead of the index by 34.11% and 25.13% when using the Linux dataset and the FSL dataset, respectively. Furthermore, compared with the state-of-the-art method HAR, EHID boosts the average backup throughput by up to a factor of 2.25 with the Linux dataset, and EHID reduces the average disk I/O traffic by up to 66.21% when it comes to the FSL dataset. EHID also marginally improves the system's restore performance.

When it comes to NAND Flash-based solid-state disks (SSDs), cache can narrow the performance gap between user-level I/Os and flash memory. Cache management schemes impose relentless impacts on the endurance and performance of flash memory. A vast majority of existing cache management techniques adopt a passive data-update style (e.g., GCaR, LCR), thereby undermining response times in burst I/O requests-based applications11.Burst I/O requests must be served in a real-time manner. This type of I/O access pattern is prevalent in data-intensive workloads.. To address this issue, we propose a collaborative active write-back cache management scheme, called Co-Active, customized for I/O access patterns and the usage status of a flash chip. We design a hot/cold separation module to determine whether data is cold or hot in workload. When a flash chip is idle, cold and dirty data in the cache is flushed into the idle flash chip to produce clean data. To curtail cache replacement cost, clean data are preferentially evicted amid the procedure of cache replacement. A maximum write-back threshold is configured according to the level of burst I/O requests in workload. This threshold is intended to avert redundant write I/Os flushing into flash memory, thereby boosting the endurance of flash memory. The experiments are conducted to validate the advantages of Co-Active in terms of average response time, write amplification, and erase count. The findings unveil that compared with the six popular cache management schemes (LRU, CFLRU, GCaR_CFLRU, LCR, and MQSim), Co-Active (1) slashes the average response time by up to 83.89 percent with an average of 32.7 percent; (2) drives up the performance cliff degree by up to 76.4 percent with an average of 42.3 percent; and (3) improves write amplification rate by up to 60.5 percent with an average of 5.4 percent.

In mobile crowdsourcing, workers are financially motivated to perform self-selected tasks to maximize their revenue. Unfortunately, the existing task scheduling approaches in mobile crowdsourcing fail to scale for massive tasks and large geographic areas. We present Turbo-GTS, a system that assigns tasks to each worker to maximize the total number of the tasks that can be completed for an entire worker group while taking into account various spatial and temporal constraints, such as task execution duration, task expiration time, and worker/task geographic locations. The core of Turbo-GTS is WBT-NNH and WBT-NUD, our two newly developed scheduling algorithms, which build on the algorithms, QT-NNH and QT-NUD, proposed in our prior work [5]. The key idea is that Turbo-GTS performs dynamic workload balancing among all workers using the proposed Workload-balancing Bisection Tree (WBT) in support of large-scale Geo-Task Scheduling (GTS). Turbo-GTS includes an interactive interface for users to load the current task/worker distributions and compare the task assignment of each worker returned by different algorithms in a real-time fashion. Using the Foursquare mobile user check-in data in New York City and Tokyo, we show the superiority of Turbo-GTS over the state of the art in terms of the total number of the tasks that can be accomplished by the entire worker group and the corresponding running time. We also demonstrate the front-end interface of Turbo-GTS with two exploratory use cases in New York City.

This paper develops a parallel computing system - MiCS - for mutual information of big categorical data on the Spark computing platform. The MiCS algorithm is conductive to processing a large amount and strong repeatability of mutual-information calculation among feature pairs by applying a column-wise transformation scheme. And to improve the efficiency of the MiCS and the utilization rate of Spark cluster resources, we adopt a virtual partitioning scheme to achieve balanced load while mitigating the data skewness problem in the Spark Shuffle process.

To cut back energy consumption of virtual-machine-powered data centers, we build an optimization model for virtual machines running in DVFS-enabled cloud data centers. With the model in place, cloud computing systems are equipped to keep track of dynamic power and static power of processors in virtual machines. Unlike existing dynamic voltage and frequency scaling schemes, our solution orchestrates frequency requirements rather than task execution times. The model makes it possible to obtain an optimal frequency ratio, which minimizes energy consumption of virtual machines. As a result, a data center's energy efficiency is boosted by controlling CPU frequency to meet the optimal frequency ratio. We demonstrate a way of manipulating frequency ratios to pushing up energy efficiency without violating virtual machines' frequency requirements. The experimental results unveil that our modeling approach offers a practical way of conserving the energy consumption of virtual machines running in data centers.

Redundancy schemes are introduced to in-memory stores to provide fault tolerance. To achieve good trade-off between access performance and memory efficiency, it is appropriate to adopt replication and erasure coding to keep popular and unpopular data, respectively. Within such a hybrid-redundancy in-memory store, an issue of redundancy transition from replication to erasure coding (a.k.a., erasure-coded archival) should be addressed for unpopular in-memory datasets, since caching workloads exhibit long-tail distributions and most in-memory data are unpopular. If data replicas are distributed across nodes in randomly-selected racks, then subsequent data-block-replica retrieval for erasure-coded archival will create cross-rack traffic, and final parity-block relocation will cause extra cross-rack communications. In this article, we propose an encoding-oriented replica placement policy - ERP - by incorporating an interleaved declustering mechanism. We design two traffic-aware erasure-coded archival schemes -TEA-TL and TEA-SL - for ERP-powered in-memory stores by taking into account temporal locality and spatial locality, respectively. With ERP in place, both TEA-TL and TEA-SL schemes embrace the following three salient features: (i) they alleviate cross-rack traffic raised by retrieving required data-block replicas; (ii) they improve rack-level load balancing by distributing replicas via load-aware primary-rack-selection approach; and (iii) they mitigate block-relocation operations launched to sustain rack-level and node-level fault-tolerance. We conduct quantitative performance evaluations using the YCSB benchmark. The empirical results show that both TEA-TL and TEA-SL schemes not only bring forth lower cross-rack traffic than the four candidate encoding schemes, but also exhibit superb archival-throughput and rack-level-balancing performance. In particular, within a group of comparative tests using the baseline configurations, TEA-TL and TEA-SL accelerate archival throughput by at least 36.3 and 70.8 percent, respectively; both TEA-TL and TEA-SL schemes improve rack-level load-balancing by a factor of more than 1.45x relative to the four candidate encoding schemes.

We propose a weighted outlier mining method called WATCH to identify outliers in high-dimensional categorical datasets. WATCH is composed of two distinctive modules: 1) feature grouping by the virtue of correlation measurement among features and 2) outlier mining by assigning scores to objects in each feature groups. At the heart of WATCH is the feature grouping module, which groups an array of features into multiple groups to discover various aspects of feature patterns in each group. The outlier mining module detects outliers from high-dimensional categorical datasets. Except for the number of outliers specified by users, WATCH is conducive to bypassing the optimization of any user-given parameter. We implement and evaluate WATCH using synthetic and real-world datasets. Our experimental results show that WATCH is a promising and practical algorithm to detect outliers in high-dimensional categorical datasets, because WATCH achieves high performance in terms of precision, efficiency, and interpretability.

In this paper, we propose a scalable mining algorithm to discover contextual outliers using relevant subspaces. We develop the mining algorithm using the MapReduce programming model running on a Hadoop cluster. Relevant subspaces, which effectively capture the local distribution of various datasets, are quantified using local sparseness of attribute dimensions. We design a novel way of calculating local outlier factors in a relevant subspace with the probability density of local datasets; this new approach can effectively reflect the outlier degree of a data object that does not satisfy the distribution of the local dataset in the relevant subspace. Attribute dimensions of a relevant subspace, and local outlier factors are expressed as vital contextual information, which improves the interpretability of outliers. Importantly, the selection of N data objects with the largest local outlier factor value is categorized as contextual outliers in our solution. To this end, our scalable mining algorithm, which incorporates the locality sensitive hashing distributed strategy, is implemented on a Hadoop cluster. The experimental results validate the effectiveness, interpretability, scalability, and extensibility of the algorithm using both synthetic data and stellar spectral data as experimental datasets.

Compared with traditional storage technologies, non-volatile memory (NVM) techniques have excellent I/O performances, but high costs and limited write endurance (e.g., NAND and PCM) or high energy consumption of writing (e.g., STT-MRAM). As a result, the storage systems prefer to utilize NVM devices as read caches for performance boost. Unlike write caches, read caches have greater potential of write reduction because their writes are only triggered by cache updates. However, traditional cache algorithms like LRU and LFU have to update cached blocks frequently because it is difficult for them to predict data popularity in the long future. Although some new algorithms like SieveStore reduce cache write pressure, they still rely on those traditional cache schemes for data popularity prediction. Due to the bad long-term data popularity prediction effect, these new cache algorithms lead to a significant and unnecessary decrease of cache hit ratios. In this paper, we propose a new Macroscopic Trend (MT) cache replacement algorithm to reduce cache updates effectively and maintain high cache hit ratios. This algorithm discovers long-term hot data effectively by observing the macroscopic trend of data blocks. We have conducted extensive experiments driven by a series of real-world traces, and the results indicate that compared with LRU, the MT cache algorithm can achieve 15.28 times longer lifetime or less energy consumption of NVM caches with a similar hit ratio.

Existing RAID-6 codes are developed to optimize either reads or writes for storage systems. To improve both read and write operations, this paper proposes a novel RAID-6 MDS array code called N-Code. N-Code exhibits three aspects of salient features: (i) read performance. N-Code assigns both horizontal parity chains and horizontal parities across disks, without generating a dedicated parity disk. Such a parity layout not only makes all the disks service normal reads, but also allows continuous data elements to share the same horizontal chain to optimize degraded reads; (ii) write performance. Diagonal parities are distributed across disks in a decentralized manner to optimize partial stripe writes, and horizontal parity chains enable N-Code to reduce I/O costs of partial stripe writes by merging I/O operations; and (iii) balancing performance. Decentralized horizontal/diagonal parities potentially support the I/O balancing optimization for single writes.

To achieve good trade-off between access performance and memory efficiency, it is appropriate to adopt replication and erasure coding to keep popular and unpopular in-memory datasets, respectively. An issue of redundancy transition from replication to erasure coding (a.k.a., erasure-coded archival) should be addressed for unpopular in-memory datasets, since caching workloads exhibit long-tail distributions and most in-memory data are unpopular.

SUMMARY: Predicting genetic regulatory variants, most of which locate in non-coding genomic regions, still remain a challenge in genetic research. Among all non-coding regulatory variants, cis-eQTL single nucleotide variants (SNVs) are of particular interest for their crucial role in regulating gene expression. Since different gene expression patterns are believed to contribute to the etiologies of different phenotypes, it is desirable to characterize the impact of cis-eQTL SNVs in a context-specific manner. Though computational methods for predicting the potential of variants being pathogenic or deleterious are well-established, methods for annotating and predicting cis-eQTL SNVs are under-developed. Here, we present TIVAN (TIssue-specific Variant ANnotation and prediction), an ensemble method of decision trees, to predict tissue-specific cis-eQTL SNVs. TIVAN is trained based on a comprehensive collection of features, including genome-wide genomic and epigenomic profiling data. As a result, TIVAN has been shown to accurately discriminate cis-eQTL SNVs from non-eQTL SNVs and perform favorably to other methods by obtaining higher five-fold cross-validation AUC values (CV-AUC) and Leave-One-Chromosome-Out predicted AUC values (LOCO-AUC) across 44 different tissues belonging to 27 different tissue classes. Finally, TIVAN consistently maintains top performance on an independent testing dataset, which includes 7 tissues in 11 studies. AVAILABILITY AND IMPLEMENTATION: TIVAN software is available at https://github.com/lichen-lab/TIVAN. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Data updates have become an important issue in erasure-coded in-memory stores owing to the two-fold reasons: (i) a handful of data-intensive in-memory stores adopt erasure coding for ‘hot’ data and (ii) small writes in update-intensive in-memory workloads cause expensive updating overheads. After delving into prior updating schemes in erasure-coded storage clusters, we investigate the applicability of these schemes to erasure-coded in-memory stores. We propose a grouped-updating mechanism—GU—to handle small writes in in-memory stores. With GU in place, requests in an updating window are categorized into several updating groups, where multiple small updates in an updating group can be concurrently executed. Two GU updating procedures—GU-stripe and GU-node—are developed to schedule updates according to a stripe and a node holding an updated data block, respectively. Furthermore, we develop two hybrid-updating schemes—Hybrid−U[GU-stripe] and Hybrid−U[GU-node]—to process common writes (i.e. small and large writes) initiated by the GU-stripe- and GU-node-based updating schemes, respectively. Replaying an update-heavy workload generated by YCSB benchmark, we extensively evaluate the four non-GU-based updating schemes, five GU-stripe-based updating schemes, and five GU-node-based updating schemes. Our experiments demonstrate that the GU mechanism boosts updating performance of small writes for RS-coded in-memory stores in terms of updating time and updating traffic. In particular, for a (8, 6) RS-coded in-memory store, the GU-stripe- and GU-node-based updating schemes shortens the updating time of the non-GU-based counterparts by a factor of at least 2.08 and 2.66, respectively. Compared to a single GU-based updating scheme, a GU-based hybrid updating scheme achieves an optimal updating-time and updating-traffic performance.

For the sake of cost-effectiveness, it is a conventional wisdom to employ (k + r,k) erasure codes to archive rarely accessed replicas, i.e. erasure-coded data archival. Existing researches on erasure-coded data archival optimizations are mainly aimed to reduce archival traffic within storage clusters. Apart from archival traffic, both non-sequential reads and imbalanced loads can deteriorate archival performance. Traditional distributed archival schemes (DArch for short) for randomly distributed replicas tend to suffer from two problems: (i) non-sequential reads because underlying file systems split a data block into multiple smaller data chunks and (ii) imbalanced loads since archival tasks are assigned according to data locality of replicas. To overcome such drawbacks, we incorporate both prefetching mechanism and balancing strategy into erasure-coded archival for replica-based storage clusters, and propose three new archival schemes: a prefetching-enabled archival scheme (i.e. P-DArch), a balancing-enabled archival scheme (i.e. B-DArch) and a prefetching-and-balancing-enabled archival scheme (i.e. PB-DArch). We implement a proof-of-concept prototype, where all the four archival schemes are deployed and quantitatively evaluated. The experimental results show that both the prefetching mechanism and balancing strategy can effectively optimize archival performance of a replica-based storage cluster exhibiting a random data layout. In a (12,9) RS-coded archival scenario, P-DArch, B-DArch and PB-DArch outperform DArch by a factor of 2.95, 1.72 and 3.85, respectively.

Parallel clustering is an important research area of big data analysis. The conventional Hierarchical Agglomerative Clustering (HAC) techniques are inadequate to handle big-scale categorical datasets due to two drawbacks. First, HAC consumes excessive CPU time and memory resources; and second, it is non-trivial to decompose clustering tasks into independent sub-tasks executed in parallel. We solve these two problems by a MapReduce-based hierarchical subspace-clustering algorithm - called PAPU - using LSH-based data partitioning. PAPU is conducive to partitioning a large-scale dataset into multiple independent sub-datasets, into which similar data objects are mapped. Advocating parallel computing, PAPU obtains sub-clusters corresponding to respective attribute subspaces from independent chunks in the local clustering phase. To improve the accuracy of approximated clustering results, PAPU measures various scale clusters by applying the hierarchical clustering scheme to iteratively merge sub-clusters during the global clustering phase. We implement PAPU on a 24-node Hadoop computing platform. The experimental results reveal that hierarchical subspace-clustering coupled with the data-partitioning strategy achieves high clustering efficiency on both synthetic and real-world large-scale datasets. The experiments also demonstrate that PAPU delivers superior performance in terms of extensibility and scalability (e.g., a nearly linear speedup).

In-memory store has become a key component for an increasing number of data-intensive applications like OLTP and OLAP. To be resilient to data loss incurred by transient failures, redundancy strategies are incorporated into in-memory stores. In-memory datasets are characterized by skewed popularity, because they exhibit varied access frequencies (a.k.a., number of accesses). Therefore, it is prudent to apply customized redundancy schemes with dynamic memory efficiency and access parallelisms to different in-memory datasets. In this work, we propose an adaptive redundancy scheme-PaRS-for in-memory datasets. PaRS relies on a re-stripe or replication mechanism to transform involved redundancy groups according to their workload popularity growth. With PaRS in place, a memory-efficient redundancy layout is deployed for data blocks with low access frequencies; a redundancy layout exhibiting high access parallelism is adopted for highly-accessed data blocks. Compared with existing redundancy schemes that employ simple replication or erasure coding, PaRS facilitates a configurable tradeoff between memory efficiency and access parallelism for in-memory data blocks. Quantitative evaluations using YCSB show that PaRS enables in-memory stores to exhibit higher access performance and memory efficiency than the replication scheme. Furthermore, PaRS achieves better load balancing than the erasure coding, while sustaining superb access performance and memory efficiency. In particular, under a double-fault-tolerant in-memory store of limited memory, PaRS improves access latency by 15.1 to 31.5 percent compared to 3-way replication, and PaRS enhances load balancing by more than 3.9× relative to Reed-Solomon coding.

Due to limited numbers of program/erase cycles (i.e., P/Es) of NAND Flash, excessive out-of-place update and erase-before-write operations wear out these P/Es during garbage collections, which adversely shorten solid state disk (i.e., SSD) lifetime. The log space in NAND Flash space of an SSD performs as an updated page ′s buffer, which lowers garbage-collection frequency while reducing consumption of P/Es to extend SSD lifetime. In this article, we propose DLSpace, a novel distributed log space allocation strategy named d istributed l og space , which divides log space into block-level log space and page-level log space to significantly optimize SSD lifetime. DLSpace′s log page space is dedicated to data pages in a data block. Such log page space only buffers page-update operations in this data block; thereby the use of log blocks for postponing garbage collection delays. DLSpace is conducive to fully utilizing pages in data and log blocks to avoid erasures of blocks with free pages. Consequently, DLSpace decreases write amplification by reducing excessive valid page-rewrite and block-erase operations under random-write-intensive workloads. We carried out quantitative research on the extension of SSD lifetime by virtue of three metrics (i.e., write amplification, the number of block-erase operations, and the delay time before the first garbage collection occurring). Experimental results reveal that compared with the existing t raditional allocation strategy for l og space (i.e., TLSpace), DLSpace reduces write amplification and the number of erase operations by up to 55.2% and 64.1% to the most extent, respectively. DLSpace also extends TLSpace′s delay time of garbage collections by 73.3% to optimize SSD lifetime.

In this study, we propose an energy-efficient database system called GreenDB running on clusters. GreenDB applies a workload-skewness strategy by managing hot nodes coupled with a set of cold nodes in a database cluster. GreenDB fetches popular data tables to hot nodes, aiming to keep cold nodes in the low-power mode in increased time periods. GreenDB is conducive to reducing the number of power-state transitions, thereby lowering energy-saving overhead. A prefetching model and an energy saving model are seamlessly integrated into GreenDB to facilitate the power management in database clusters. We quantitatively evaluate GreenDB's energy efficiency in terms of managing, fetching, and storing data. We compare GreenDB's prefetching strategy with the one implemented in Postgresql. Experimental results indicate that GreenDB conserves the energy consumption of the existing solution by up to 98.4 percent. The findings show that the energy efficiency of GreenDB can be optimized by tuning system parameters, including table size, hit rates, number of nodes, number of disks, and inter-arrival delays.

The goal of this study is to optimize energy efficiency of database clusters through prefetching and caching strategies. We design a workload-skewness scheme to collectively manage a set of hot and cold nodes in a database cluster system. The prefetching mechanism fetches popular data tables to the hot nodes while keeping unpopular data in cold nodes. We leverage a power management module to aggressively turn cold nodes in the low-power mode to conserve energy consumption. We construct a prefetching model and an energy-saving model to govern the power management module in database lusters. The energy-efficient prefetching and caching mechanism is conducive to cutting back the number of power-state transitions, thereby offering high energy efficiency. We systematically evaluate energy conservation technique in the process of managing, fetching, and storing data on clusters supporting database applications. Our experimental results show that our prefetching/caching solution significantly improves energy efficiency of the existing PostgreSQL system.

It is not uncommon for reconstruction I/Os to encounter workload fluctuation in heterogeneous RAID-coded storage systems. This paper proposes a heterogeneity-aware single-failure recovery scheme—SmartRec—to tolerate double and multiple disk failures in RAIDs. We start this study by formulating the data recovery problem of single-disk failures in form of an optimization function in the context of online and heterogeneous disk arrays. To take both static heterogeneity associated with disk configurations and dynamic heterogeneity affected by I/O loads into account, SmartRec periodically selects an appropriate reconstruction solution according to up-to-date disk utilization. The appropriate reconstruction solution indicates the amount of data being retrieved across surviving disks and is expected to achieve minimal recovery time, which is induced by both candidate reconstruction sequences and reconstruction I/O capability of surviving disks. We build a response-time model in SmartRec to measure the reconstruction I/O capability of surviving disks during a recovery process. To quantitatively compare the SmartRec scheme against three alternatives (i.e. ConRec, MinRec and BalRec), we build four analytical models and validate the correctness of the four models using empirical evaluations. We implement the four reconstruction schemes in a heterogeneous RAID, and carry out comparative online reconstruction tests by replaying real-world workloads under various configurations. The experimental results illustrate that our SmartRec scheme outperforms the three existing reconstruction schemes in terms of reconstruction time by up to 35.3% with an average of 25.8%.

Data in a high-dimensional data space may reside in a low-dimensional manifold embedded within the high-dimensional space. Manifold learning discovers intrinsic manifold data structures to facilitate dimensionality reductions. We propose a novel manifold learning technique called fast [Formula: see text] selection for locally linear embedding or FSLLE, which judiciously chooses an appropriate number (i.e., parameter [Formula: see text]) of neighboring points where the local geometric properties are maintained by the locally linear embedding (LLE) criterion. To measure the spatial distribution of a group of neighboring points, FSLLE relies on relative variance and mean difference to form a spatial correlation index characterizing the neighbors’ data distribution. The goal of FSLLE is to quickly identify the optimal value of parameter [Formula: see text], which aims at minimizing the spatial correlation index. FSLLE optimizes parameter [Formula: see text] by making use of the spatial correlation index to discover intrinsic structures of a data point’s neighbors. After implementing FSLLE, we conduct extensive experiments to validate the correctness and evaluate the performance of FSLLE. Our experimental results show that FSLLE outperforms the existing solutions (i.e., LLE and ISOMAP) in manifold learning and dimension reduction. We apply FSLLE to face recognition in which FSLLE achieves higher accuracy than the state-of-the-art face recognition algorithms. FSLLE is superior to the face recognition algorithms, because FSLLE makes a good tradeoff between classification precision and performance.

Due to the nonlinear deformation of nonrigid and nonuniform tissues, it is challenging to accurately measure the displacements of feature points distributed on the inner parts, boundaries, and separatrices of tissue layers. To address this challenge, we propose a feature point matching technique called RAPID to measure MR 2D slice deformation of nonuniform and nonrigid biological tissues. We propose to use the covariance of several neighboring point statistics computed around a keypoint, as the keypoint descriptor. Inspired by the kernel methods, we advocate adopting a Riemannian pseudo kernel to map SPD matrices to a high dimensional Hilbert space, where the Euclidean geometry applies. We compare our RAPID with two existing schemes (i.e., SIFT and SURF). Our experimental results show that our RAPID is superior to SIFT and SURF, because the benefits offered by RAPID are two-fold. First, our RAPID increases the number of matched data points. Second, RAPID substantially improves the key-point matching accuracy of SIFT and SURF.

In this study, we discover that the data skewness problem imposes adverse impacts on MapReduce-based parallel kNN-join operations running clusters. We propose a data partitioning approach-called kNN-DP-to alleviate load imbalance incurred by data skewness. The overarching goal of kNN-DP is to equally divide data objects into a large number of partitions, which are processed by mappers and reducers in parallel. At the heart of kNN-DP is a data partitioning module, which dynamically and judiciously partitions data to optimize kNN-join performance by suppressing data skewness on Hadoop clusters. Data partitioning decisions largely depends on data properties (e.g., distributions), the analysis of which is highly expensive for a massive amount of data. To speed up the data-property analysis, we incorporate a sampling technique to profile the data distribution of a small sample dataset representing big datasets. After building a data-partitioning cost model for parallel kNN-joins, we derive the time-complexity upper and lower bounds of parallel kNN-join algorithms. The cost model offers us a guidance to systematically investigate kNN-DP's performance. kNN-DP obtains global nearest neighbors using local nearest neighbors. To improve the accuracy of such an approximation solution, we augment each node's local data by a small amount of redundant data. We develop two kNN-DP-based schemes called LSH+ and z-value+, which seamlessly integrate kNN-DP with the existing LSH and z-value algorithms for kNN-join computing. We implement and evaluate LSH+ and z-value+ on a 24-node Hadoop cluster driven by both synthetic and real-world high-dimensional datasets. The experimental results show that kNN-DP significantly improves the performance of LSH and z-value while offering high extensibility and scalability on Hadoop clusters.

In mobile crowdsourcing, workers are financially motivated to perform as many self-selected tasks as possible to maximize their revenue. Unfortunately, the existing task scheduling approaches in mobile crowdsourcing fail to consider task execution duration and do not scale for massive tasks and large geographic areas (e.g., a whole city). In this paper, we study on the geo-task scheduling problem (GTS) under the various spatial and temporal constraints in real-world mobile crowdsourcing applications, including task execution duration and task expiration time. Given the location of a worker, the goal of our study is to find an optimal task execution sequence that maximizes the number of tasks that could be finished. Since the exact solution to the maximum task scheduling is computationally intractable, we propose two sub-optimal approaches (LCPF and NUD-IC) based on the particle filtering and the DBSCAN clustering.

As issues of the Energy Wall and the Reliability Wall become unavoidable, it is a demanding and challenging task to reduce energy consumption in large-scale storage systems in modern data centres while retaining acceptable systems reliability. Most energy conservation techniques inevitably have adverse impacts on the parallel disk systems. To address the reliability issues of energy-efficient parallel storage systems, we propose a reliable energy-efficient storage system called DuoFS, which aims at improving both energy efficiency and reliability of parallel storage systems by seamlessly integrating HDDs and SSDs. With the help of the middleware layer, DuoFS can distribute popular data to SSD-based nodes and put HDD-based nodes into the low-power mode under light workload conditions without modification of the parallel systems.

Data-intensive applications are increasingly depending on in-memory stores to meet high-I/O-performance requirements. To be resilient to server failures and in turn achieve high availability, both replication and erasure codes are introduced to in-memory stores. Since erasure codes have an advantage of memory efficiency over replication, we focus our work on erasure-coded in-memory stores and investigate placement schemes to address the issue of workload fluctuation. To mitigate the I/O imbalanced incurred by workload skew and maximize the utilization of all nodes, we proposed a Workload-aware Placement Scheme called WPS for Reed-Solomon-coded in-memory stores. WPS accomplishes balanced I/Os as follows: it divides in-memory data blocks into multiple groups based on access characteristics (e.g., popularity), and classifies all nodes into several groups according to nodes' access performance (e.g., indicated by available bandwidth), and places or migrates high-access-popularity in-memory data blocks to high-performance nodes without violating the essential principle of fault tolerance. The comparative experiments indicate that WPS can significantly improve load balancing for RS-coded in-memory stores exhibiting workload popularity skew; meanwhile, WPS achieves comparable mean, median, and tail latencies relative to two candidate placement schemes.

Erasure coding has been gradually adopted by existing data-intensive in-memory stores for 'hot' data; small writes lead to expensive updating overheads in such in-memory stores characterized by update-heavy workloads. There is a pressing demand to address the issue of data updates for erasure-coded in-memory stores. We revisit existing updating schemes in erasure-coded storage clusters by investigating the applicability of these updating schemes to erasure-coded in- memory stores. After an intensive analysis, we propose a grouping-update mechanism - GU - to handle small writes in in-memory stores. With GU in place, requests in an updating window are categorized into several updating groups, where multiple small updates in the same stripe can be executed concurrently. Furthermore, we bring forward a hybrid-updating scheme - Hybrid-U - to minimize total updating I/Os over network under common writes (e.g., small and large writes). We evaluate four dedicated updating schemes, four GU- based updating schemes and Hybrid-U. Our experiments illustrate that GU-based updating schemes and Hybrid-U outperform the four dedicated updating schemes in terms of updating time.

Summary Cluster‐level thermal management has gained much attention over the past decade due to rising cooling costs associated with data centers. In this research, we propose and implement a static scheduler called SSched and a dynamic one named DSched. These 2 algorithms schedule jobs based on CPU and disk temperatures of a Hadoop cluster's nodes. Our schedulers rely on a monitoring mechanism to keep track of CPU and disk utilization, maintaining CPU and disk temperatures below a threshold through thermal‐aware scheduling decisions. To facilitate the design of SSched and DSched, we classify jobs into the CPU‐intensive and disk‐intensive categories. When a job arrives, SSched retrieves the utilization stats from a profiled log, estimates the thermal behavior, and places the job on NodeManager to minimize thermal impacts. Unlike SSched, DSched improves thermal efficiency of Hadoop clusters through dynamic load balancing. DSched keeps track of the coolest and hottest nodes in the cluster; tasks are migrated from hot nodes into cool ones if any hot spot is detected. To evaluate the effectiveness of our schedulers, we keep track of average CPU and disk temperatures in a node, managing an optimal outlet temperature across a cluster. We demonstrate that compared with the traditional Hadoop scheduler, SSched and DSched achieve approximately 15% savings in terms of cooling cost with little performance overhead.

In this paper, we propose an erasure-coded data archival system called aHDFS for Hadoop clusters, where RS(k + r; k) codes are employed to archive data replicas in the Hadoop distributed file system or HDFS. We develop two archival strategies (i.e., aHDFS-Grouping and aHDFS-Pipeline) in aHDFSto speed up the data archival process. aHDFS-Groupinga MapReduce-based data archiving scheme - keeps each mapper's intermediate output Key-Value pairs in a local key-value store. With the local store in place, aHDFS-Grouping merges all the intermediate key-value pairs with the same key into one single key-value pair, followed by shuffling the single Key-Value pair to reducers to generate final parity blocks. aHDFS-Pipeline forms a data archival pipeline using multiple data node in a Hadoop cluster. aHDFS-Pipeline delivers the merged single key-value pair to a subsequent node's local key-value store. Last node in the pipeline is responsible for outputting parity blocks. We implement aHDFS in a real-world Hadoop cluster. The experimental results show that aHDFS-Grouping and aHDFS-Pipeline speed up Baseline's shuffle and reduce phases by a factor of 10 and 5, respectively. When block size is larger than 32 MB, aHDFS improves the performance of HDFS-RAID and HDFS-EC by approximately 31.8 and 15.7 percent, respectively.

Traditional parallel algorithms for mining frequent itemsets aim to balance load by equally partitioning data among a group of computing nodes. We start this study by discovering a serious performance problem of the existing parallel Frequent Itemset Mining algorithms. Given a large dataset, data partitioning strategies in the existing solutions suffer high communication and mining overhead induced by redundant transactions transmitted among computing nodes. We address this problem by developing a data partitioning approach called FiDoop-DP using the MapReduce programming model. The overarching goal of FiDoop-DP is to boost the performance of parallel Frequent Itemset Mining on Hadoop clusters. At the heart of FiDoop-DP is the Voronoi diagram-based data partitioning technique, which exploits correlations among transactions. Incorporating the similarity metric and the Locality-Sensitive Hashing technique, FiDoop-DP places highly similar transactions into a data partition to improve locality without creating an excessive number of redundant transactions. We implement FiDoop-DP on a 24-node Hadoop cluster, driven by a wide range of datasets created by IBM Quest Market-Basket Synthetic Data Generator. Experimental results reveal that FiDoop-DP is conducive to reducing network and computing loads by the virtue of eliminating redundant transactions on Hadoop nodes. FiDoop-DP significantly improves the performance of the existing parallel frequent-pattern scheme by up to 31 percent with an average of 18 percent.

Caching and prefetching are effective approaches to boosting the performance of metadata access in distributed storage systems. Many research efforts have been devoted in developing new metadata prefetching methods by considering past file access patterns. However, the existing methods do not consider the correlations between processes and the corresponding files(e.g. file provenance). Therefore, the methods cannot obtain very rich and accurate correlations, thus decreasing the effectiveness of metadata prefetching. This paper presents a Provenance-based Metadata Prefetching(ProMP) scheme, which considers both provenance and the past file access patterns. Through mining the correlations between processes and corresponding files from provenance and past access history, ProMP can achieve accurate and rich correlation information. ProMP is conducive to employing aggressive metadata prefetching to boost the performance by leveraging the correlations. Our experimental results show that ProMP performs more effectively with less memory overhead than the existing solutions, while improving the hit rates by up to 49% and 7% in contrast to traditional LRU and a state-of-art metadata prefetching algorithm Nexus, respectively.

MapReduce is a widely adopted computing framework for data-intensive applications running on clusters. We propose an approach to exploit data parallelisms in XML processing using MapReduce in Hadoop. Our solution seamlessly integrates data storage, labelling, indexing, and parallel queries to process a massive amount of XML data. Specifically, we introduce an SDN labelling algorithm and a distributed hierarchical index using DHTs, we develop an efficient data retrieval approach called B-SLCA. More importantly, we design an advanced two-phase MapReduce solution that is able to efficiently address the issues of labelling, indexing, and query processing on big XML data. We implemented our solution on a real-world Hadoop cluster processing the real-world datasets. Our experimental results show that SDN outperforms NCIM by up to a factor of 1.36 with an average of 1.17, our BSLCA outperforms BwdSLCA by up to a factor of 1.96 with an average of 1.2.

Extracting high I/O performance from parallel file systems is no longer the only goal in modern data centres. As issues of the Energy Wall and the Reliability Wall become unavoidable, it is a demanding and challenging task to reduce energy consumption in large-scale storage systems in modern data centres while retaining acceptable systems reliability. Most energy conservation techniques inevitably have adverse impacts on the parallel disk systems. To address the reliability issues of energy-efficient parallel storage systems, we propose a reliable energy-efficient storage system called RESS, which aims at improving both energy efficiency and reliability of parallel storage systems by seamlessly integrating HDDs and SSDs. At the heart of the RESS is a transformative middleware layer, which reorganizes the I/O workload for the underlying parallel file systems. With the help of the middleware layer, RESS can distribute popular data to SSDs and put HDDs into the low-power mode under light workload conditions without modification of the parallel systems.

Energy saving is rapidly becoming one of the hottest topics in technology field within recent decades. With the development of technology, it brings a sheer increasing trend of data and the growth scale of clusters and data centers. Meanwhile, it also raises another essential issue into the path: energy cost. In this paper, we are diving into this key issue and evaluating energy- efficiency based on TPC-W benchmark: a notable web transaction e-commerce benchmark. We simulate the web transaction with different database sizes and collect the energy data by KILL-A-WATT. Also, we deploy this setup on four different cluster systems: PC nodes and wimpy nodes, and two different heterogeneous systems: using PC as front server and wimpy as Database server, and using wimpy as Web server and PC as Database server. Energy result demonstrates different characteristics among them, which can give lightening advice for future works in data center.

Existing distance-based outlier mining methods do not consider the impact of each attribute's importance degree, thereby resulting in poor mining accuracies. To address this problem, we propose a new outlier mining algorithm – Miner* – that makes use of information entropy and Weighted Distance Sum to substantially improve mining accuracies. Miner* employs information entropy to determine weight values indicating the importance degrees of data attributes. An input dataset is reduced by Miner* through the neighbour-radius-based pruning technologies. Thus, Miner* obtains a candidate outlier set by removing any data objects that are unlikely to be outliers. Miner* calculates the weighted distance sum value Wkof each object in the candidate outlier set; Wkvalue ranks the top n to be regarded as outliers. Due to the sum of distance, which takes full advantage of the clustering characteristics of the dataset, edge distribution data objects and local outliers can be effectively mined out. To demonstrate the effectiveness of the Miner* algorithm, we implement Miner* in a prototype system to detect star spectrum data objects with abnormal characteristic lines. Our experimental results show that the algorithm in Miner* achieves high accuracy, high scalability, and low man-made influence by utilizing UCI and star spectrum dataset. Our results also confirm that Miner* is feasible and effective in mining spectrum data with abnormal characteristic lines from massive star spectrum dataset.

Abstract Location privacy protection in vehicular ad hoc networks considers preserving two types of information: the locations and identifications of users. However, existing solutions, which either replace identifications by pseudonyms or hide locations in areas, cannot be directly applied to geographic routing protocols because they degrade network performance. To address this issue, we proposed a location‐preserved contention (LPC) based routing protocol, in which greedy forwarding is achieved using dummy distance to the destination information instead of users’ true locations. Unlike the contention‐based forwarding protocol, the number of duplicated responses in LPC can be reduced by adjusting the parameterα, which is a timer scaling factor. To quantify the efficiency of location privacy protection, an entropy‐based analytical method is proposed. LPC is compared with existing routing and location privacy protection protocols in simulations. Results show that LPC provides 11.7% better network performance and a higher level of location privacy protection than the second best protocol. Copyright © 2014 John Wiley & Sons, Ltd.

In this paper, we present a thermal-aware file assignment technique called TIGER for reducing the cooling cost of storage clusters in data centers. We show that peak inlet temperatures of storage nodes depend on not only CPU utilization but also I/O activities, which rely on file assignments in a cluster. The TIGER scheme aims to lower peak inlet temperatures of storage clusters by dynamic thermal management through file placements. TIGER makes use of cross-interference coefficients to estimate the re-circulation of hot air from the outlets to the inlets of data nodes. TIGER first calculates the thresholds of disks in each data node based on its contribution to heat re-circulation in a data center. TIGER undertakes two steps to achieve high I/O performance while reducing cooling cost. First, TIGER assigns groups of files with similar service times to shorten I/O response times. Second, TIGER ensures that load imbalance does not exceed a specified threshold. We evaluate performance of TIGER in terms of both cooling energy conservation and response time of a storage cluster. Our results confirm that TIGER reduces cooling-power requirements for clusters by offering about 10 to 15 percent cooling-energy savings without significantly degrading I/O performance.

This research develops an advanced two-phase MapReduce solution that is able to efficiently address skyline queries on large datasets. Unlike existing parallel skyline approaches, our scheme considers data partitioning, filtering, and parallel skyline evaluation as a holistic query process. In particular, we apply filtering techniques and angle-based partitioning in the first phase, in which unqualified objects are discarded and the processed objects are partitioned by their angles to the origin.In the second phase, local skyline objects in each partition are calculated in parallel, and global skyline objects are output after a merging skyline process. To improve the parallel local skyline calculation, we propose two partition-aware filtering methods that keep skyline candidates in a balanced manner. The aggressive partition-aware filtering aggressively eliminates objects in the partition with the greatest population of candidate objects, whereas the proportional partition-aware filtering slows down the growth of partition population proportionally. Recognizing the lack of studies that incorporate the MapReduce framework into parallel skyline processing, we propose a partialpresort grid-based partition skyline algorithm that is able to significantly improve the merging skyline computation on large datasets. The presort process can be completed in the shuffle phase with little overhead. Our experimental results show the efficiency and effectiveness of the proposed parallel skyline solution utilizing MapReduce on large-scale datasets.

Existing parallel mining algorithms for frequent itemsets lack a mechanism that enables automatic parallelization, load balancing, data distribution, and fault tolerance on large clusters. As a solution to this problem, we design a parallel frequent itemsets mining algorithm called FiDoop using the MapReduce programming model. To achieve compressed storage and avoid building conditional pattern bases, FiDoop incorporates the frequent items ultrametric tree, rather than conventional FP trees. In FiDoop, three MapReduce jobs are implemented to complete the mining task. In the crucial third MapReduce job, the mappers independently decompose itemsets, the reducers perform combination operations by constructing small ultrametric trees, and the actual mining of these trees separately. We implement FiDoop on our in-house Hadoop cluster. We show that FiDoop on the cluster is sensitive to data distribution and dimensions, because itemsets with different lengths have different decomposition and construction costs. To improve FiDoop's performance, we develop a workload balance metric to measure load balance across the cluster's computing nodes. We develop FiDoop-HD, an extension of FiDoop, to speed up the mining performance for high-dimensional data analysis. Extensive experiments using real-world celestial spectral data demonstrate that our proposed solution is efficient and scalable.

This paper presents a model-predictive control-based scheduling strategy called ThermoRing to reduce cooling costs in data centers. ThermoRing makes use of an online feedback control mechanism to improve thermal management of energy-efficient clusters in a data center. ThermoRing aims at keeping the maximum inlet temperatures of the nodes under a redline temperature limit with little stability errors. Importantly, the ThermoRing approach is capable of dealing with emergency conditions (e.g., node fan shutdown and unexpected rising task arrival rates) by dynamically balancing load among the nodes. ThermoRing incorporates a heat distribution matrix to model the thermal characteristics of a data center housing cluster. ThermoRing is conducive to thermal management in data centers with high-scheduling performance and stability. Using a real-world online bookstore trace, we conduct extensive experiments to compare the performance of ThermoRing with three existing solutions (i.e., C-Oracle, Ad-hoc, and MinHR). The experimental results show that ThermoRing improved the system throughput by more than 10% under regular load conditions and by 40% in emergency cases. ThermoRing also significantly improves the energy efficiency of MinHR, which is a thermal-aware scheduler.

In this demonstration, we present a visualization system offering two advanced solutions that can efficiently address a novel multi-criteria optimal location query by using Overlapping Voronoi Diagrams (OVDs). Our system not only displays an example that applies the advanced solutions to a practical optimal location query, but also visualizes the process of query evaluation by using the solutions, which can help users better understand the two solutions in a more intuitive way. The Real Region as Boundary (RRB) approach calculates real regions of overlapped Voronoi cells, while the Minimum Bounding Rectangle as Boundary (MBRB) approach approximates the cells by their MBRs to simplify region overlapping calculation. For efficient query evaluation and better demonstration, global and local datasets are managed separately and only the local dataset is displayed in a limited visualization area. User interactions are provided in diverse manners in our system by using the Standard Widget Toolkit (SWT) and Open Graphics Library (OpenGL).

It is indispensable to speed up a reconstruction process in erasure-coded storage clusters, because a fast data recovery helps to shorten the vulnerability window while improving storage system reliability. To address double- and multiple-node failures, this paper proposes a cooperative reconstruction pattern - CoRec - to minimize reconstruction traffic. CoRec not only enables all rebuilding nodes to collaboratively reconstruct failed blocks but also limits each surviving block to be transferred over network only once. To clarify two CoRec based reconstruction schemes (i.e., CoRec-rn and CoRec-sn), we investigate two alternative reconstruction schemes (i.e., CRec and DRec). We develop reconstruction-time models, which are validated using empirical data, to estimate reconstruction performance of large-scale storage clusters and to pinpoint performance bottlenecks in the reconstruction process. We implement a proof-of-concept prototype where the four reconstruction schemes are quantitatively evaluated. Experimental results show that CoRec-rn and CoRec-sn significantly reduce the reconstruction time of CRec and DRec. In a real-world 9-node storage cluster, CoRec-rn speeds up the double-node reconstruction of CRec and DRec by a factor of at least 1.72, CoRec-sn accelerates the double-node reconstruction of CRec and DRec by a factor of at least 4.76.

Recent studies indicate that the energy cost and carbon footprint of data centers have become exorbitant. It is a demanding and challenging task to reduce energy consumption in large-scale storage systems in modern data centers. Most energy conservation techniques inevitably have adverse impacts on parallel disk systems. To address the reliability issues of energy-efficient parallel disks, we propose a reliable energy-efficient RAID system called REED, which aims at improving both energy efficiency and reliability of RAID systems by seamlessly integrating HDDs and SSDs. At the heart of REED is a high-performance cache mechanism powered by SSDs, which are serving popular data. Under light workload conditions, REED spins down HDDs into the low-power mode, thereby offering energy conservation. Importantly, during an I/O access turbulence (i.e., I/O load is dynamically and frequently changing), REED is conducive to reducing the number of disk power-state transitions by keeping HDDs in the low-power mode while serving requests with SSDs. We build a model to quantitatively show that REED is capable of improving the reliability of energy-efficient RAIDs. We implement the REED prototype in a real-world RAID-0 system. Our experimental results demonstrate that REED improves the energy-efficiency of conventional RAID-0 by up to 73% while maintaining good reliability.

Highly available cloud storage is often implemented with complex, multi-tiered distributed systems built on top of clusters of commodity servers and disk drives. Storage reliability, security and performance are among the top desired features when clients consider storing data on cloud storage. Although replication improves reliability and performance in cloud storage systems, data replication increases the risk of data storage in an insecure network environment. When a cloud storage scales up, storage nodes are very likely to become heterogeneous in nature. In this study, we propose a secure replica allocation scheme called SecRA to improve security, reliability, and performance of a cloud storage system where storage nodes have a wide variety of vulnerabilities. Our SecRA integrates the techniques of replication and fragmentation with secret sharing in a heterogeneous cloud system, where storage nodes are comprised of various server types in terms of vulnerability characteristics. SecRA allocates data replicas of fragments of a file to as many different types of nodes as possible. For the replicas of the same fragment, SecRA tries to allocate these replicas to the same type of nodes in the system. Data assurance is significantly improved, because the replicas of different fragments of a file are allocated to multiple types of storage nodes. To quantitatively evaluate the quality of security offered by SecRA, we develop a storage assurance model. Our analytically results show that replica allocations made by SecRA lead to enhanced security thanks to the consideration of heterogeneous vulnerabilities in cloud storage systems.

RAID-6 is widely applied to tolerate double concurrent disk failures in both disk arrays and storage clusters. Among numerous erasure codes developed to implement RAID-6, Maximum Distance Separable (MDS) Codes are highly popular. Owing to the limitation of parity generating schemes used in MDS codes, RAID-6-based storage systems suffer from unbalance I/Os and low reconstruction performance. Out of consideration for high performance and reliability, we propose a new class of XOR-based RAID-6 code (i.e. |$V^{2}$|-Code), which improves both load balancing and reconstruction performance of the MDS RAID-6 codes. |$V^{2}$|-Code, a very simple yet flexible Non-MDS vertical code, can be easily implemented and deployed in storage systems. |$V^{2}$|-Code's unique features include lowest density code, steady parity chain length and well-balanced computation. We perform theoretical analysis and empirical evaluation of the coding scheme by running a wide range of workload under various configurations. Experimental results show that |$V^{2}$|-Code outperforms four popular codes (i.e. EVENODD, RDP, X-Code and Code-M) in terms of load balancing and reconstruction time. In the single-disk-failure and double-disk-failure cases, |$V^{2}$|-Code can speed up the reconstruction time of X-Code by a factor of up to 3.31 and 1.79, respectively.

Serving as cache disks, flash-based solid-state drives (SSDs) can significantly boost the performance of read-intensive applications. However, frequent data updating, the necessary condition for classical replacement algorithms (e.g., LRU, MQ, LIRS, and ARC) to achieve a high hit rate, makes SSDs wear out quickly. To address this problem, we propose a new approach—write-efficient caching (WEC)—to greatly improve the write durability of SSD cache. WEC is conducive to reducing the total number of writes issued to SSDs while achieving high hit rates. WEC takes two steps to improve write durability and performance of SSD cache. First, WEC discovers write-efficient data, which tend to be active for a long time period and to be frequently accessed. Second, WEC keeps the write-efficient data in SSDs long enough to avoid excessive number of unnecessary updates. Our findings based on a wide range of popular real-world traces show that write-efficient data does exist in a wide range of popular read-intensive applications. Our experimental results indicate that compared with the classical algorithms, WEC judiciously improves the mean hits of each written block by approximately two orders of magnitude while exhibiting similar or even higher hit rates.

This paper addresses an I/O interference problem encountered in on-line reconstruction of erasure-coded storage clusters, where user I/Os compete with reconstruction I/Os for both disk and network bandwidth. We propose a redirection scheme called `RAM-RS' to minimize the I/O interference among user and reconstruction requests. RAM-RS redirects user read/writes targeted at failed nodes to an RS-coded RAM region, which is formed by pre-allocated main memory in surviving nodes in the RS-coding manner. The RS-coded RAM region quickly serves all user read/write misses; therefore, a rebuilding node can devote its disk and network bandwidths to the node reconstruction. The RAM region substantially reduces the amount of data rebuilt by the rebuilding node, because (1) missed writes are buffered in the RAM region and (2) missed reads are satisfied by using surviving nodes to co-rebuild failed blocks. We build two Markov models to estimate the reliability of the RAM-RS system. Modeling results demonstrate that the MTTDL of RS-coded RAM region in a storage cluster is larger than that of the same cluster comprised of surviving nodes. We implement both RAM-RS and the traditional Redirection schemes in an erasure-coded storage cluster, on which real-world I/O traces are replayed. Experimental results show that compared with the Redirection scheme running on a 9-node storage cluster, RAM-RS improves system performance in terms of both user response time and reconstruction time by a factor of 1.78 and 1.20, respectively.

A large write amplification ratio degrades the program/erase cycles (P/Es) of NAND Flashes and reduces the endurance and performance of solid state disks (SSDs). The lack of a practical way to measure write amplification for SSDs motivates us to propose a novel measuring method called RB-Explorer at the SSD level rather than the NAND Flash level. The goal of RB-Explorer is two-fold: (1) to accurately measure the write amplification of SSDs to quantify SSD endurance and (2) to study the impacts of I/O techniques on write amplification of SSDs. RB-Explorer incorporates a Ready/Busy (R/B) signal of one of the NAND Flashes in an SSD in a proposed write amplification model for SSDs with four full-parallelism levels (i.e., the channel, chip, die, and plane levels). RB-Explorer takes two steps toward measuring write amplification. First, RB-Explorer quantifies the number of page programs using the low R/B signal level, the duration of which varies with the different operation (i.e., read, program, and erase) in NAND Flash. Second, RB-Explorer measures data volume written to NAND Flashes by considering parallelisms at four levels. Data volume written to a die in a NAND Flash is obtained as a product of the number${\rm N_{p}}$of programs and page size${\rm P_{a}}$. Given the number${\rm N_{channel}}$of channels, the number${\rm N_{chip}}$of chips per channel, and the number${\rm N_{die}}$of dies per chip, one can obtain the data volume written to NAND Flashes as a product of${\rm N_{p}}, {\rm P_{a}}, {\rm N_{die}}, {\rm N_{chip}}$, and${\rm N_{channel}}$. RB-Explorer is applied to analyzing write amplification ratios of SSDs to track SSD endurance. Furthermore, we implement a real-world SSD (i.e., SSD-v) and employ a fine-tuned SSD simulator (i.e., SSDsim) to validate the accuracy of RB-Explorer. Our experimental results show that RB-Explorer improves on the accuracy of SSDsim—the state-of-the-art SSD simulator—in most tested cases. We conduct a series of measurements using micro-benchmarks and I/O traces to demonstrate how RB-Explorer may be applied to investigate SSDs.

This article presents a framework, Frog, for Context-Based File Systems (CBFSs) that aim at simplifying the development of context-based file systems and applications. Unlike existing informed-based context-aware systems, Frog is a unifying informed-based framework that abstracts context-specific solutions as views, allowing applications to make view selections according to application behaviors. The framework can not only eliminate overheads induced by traditional context analysis, but also simplify the interactions between the context-based file systems and applications. Rather than propagating data through solution-specific interfaces, views in Frog can be selected by inserting their names in file path strings. With Frog in place, programmers can migrate an application from one solution to another by switching among views rather than changing programming interfaces. Since the data consistency issues are automatically enforced by the framework, file-system developers can focus their attention on context-specific solutions. We implement two prototypes to demonstrate the strengths and overheads of our design. Inspired by an observation that there are more than 50% of small files (<4KB) in a file system, we create a Bi-context Archiving Virtual File System (BAVFS) that utilizes conservative and aggressive prefetching for the contexts of random and sequential reads. To improve the performance of random read-and-write operations, the Bi-context Hybrid Virtual File System (BHVFS) combines the update-in-place and update-out-of-place solutions for read-intensive and write-intensive contexts. Our experimental results show that the benefits of Frog-based CBFSs outweigh the overheads introduced by integrating multiple context-specific solutions.

A key design goal of erasure-coded storage clusters is to minimize reconstruction time, which in turn leads to high reliability by reducing vulnerability window size. PULL-Rep and PULL-Sur are two existing reconstruction schemes based on PULL-type transmission, where a rebuilding node initiates reconstruction by sending a set of read requests to surviving nodes to retrieve surviving blocks. To eliminate the transmission bottleneck of replacement nodes in PULL-Rep and mitigate the extra overhead caused by noncontiguous disk access in PULL-Sur, we incorporate PUSH-type transmissions to node reconstruction, where the reconstruction procedure is divided into multiple tasks accomplished by surviving nodes in a pipelining manner. We also propose two PUSH-based reconstruction schemes (i.e., PUSH-Rep and PUSH-Sur), which can not only exploit the I/O parallelism of PULL-Sur, but also maintain sequential I/O accesses inherited from PULL-Rep. We build four reconstruction-time models to study the reconstruction process and estimate the reconstruction time of the four schemes in large-scale storage clusters. We implement a proof-of-concept prototype where the four reconstruction schemes are deployed and quantitatively evaluated. Experimental results show that the PUSH-based reconstruction schemes outperform the PULL-based counterparts. In a real-world (9,6)RS-coded storage cluster, PUSH-Rep speeds up the reconstruction time by a factor of 5.76 compared with PULL-Rep; PUSH-Sur accelerates the reconstruction by a factor of 1.85 relative to PULL-Sur.

It is indispensable to scale erasure-coded storage clusters to meet requirements of increased storage capacity and I/O performance. In this study, we propose an efficient scaling scheme for Reed-Solomon-coded storage clusters called Scale-RS, which has three salient features. First, Scale-RS achieves uniform data distribution by equally placing data blocks among old and new chunks using a transposed data layout. Second, Scale-RS minimizes data movement incurred in the procedures of data redistribution and parity update. Scale-RS not only reaches the lower bound of data migration traffic by transferring necessary data blocks from old data chunks to new chunks, but it also reduces update traffic via generating parity difference blocks from data blocks stored in an individual data chunk. Third, Scale-RS improves the I/O performance of scaled storage clusters in terms of read parallelism and write throughput. We implement Scale-RS along with two alternative scaling schemes in a Reed-Solomon-coded storage cluster, on which real-world I/O traces are replayed. Experimental results demonstrate that Scale-RS achieves the highest read performance among the three scaling schemes after data redistribution. When it comes to scaling from six data chunks to nine, Scale-RS can outperform the other two scaling schemes in terms of aggregate write throughput by a factor of 2.85 and 3.05 under online filling and offline filling, respectively. We also show that user response time is slightly enlarged during data redistribution due to bandwidth competition between migration and user I/Os.

This paper addresses an issue of erasure-coded data archival, where (k + r; k) erasure codes are employed to archive rarely accessed replicas. The traditional synchronous encodingprocess neither leverages the existence of replicas, nor handles encoding operations in a decentralized manner. To overcome these drawbacks, we exploit pipelined encoding processes to boost the data archival performance on storage clusters. First, we propose two data layouts called [D + P]cdand [3X]cdby applying a chained-declustering mechanism to both Mirrored RAID-5 and triplication redundancy groups. Second, in light of the [D + P]cdand [3X]cdlayouts, we design two archiving schemes named DP and 3X, which exhibit the following three salient features: (i) exploiting data locality-two or three local blocks are read by each involved node for encoding; (ii) decentralized computation load-encoding operations are distributed among k nodes; and (iii) parallel archival processing-two or three encoding pipelines are simultaneously deployed to generate parity blocks. We implement both the DPand 3X schemes and three existing solutions (i.e., SynE, DE, and RapidRAID) in a real-world storage cluster. Experimental results show that our archival schemes outperform the other three solutions in terms of archiving time by a factor of at least 3.41 in a nine-node storage cluster. The experiments strongly indicate that the performance bottleneck of SynE lies in its block-receiving stage; it is disk I/O rather than network traffic that dominates archiving time for both the DE and RapidRAID schemes.

The diagnosability of a system is defined as the maximum number of faulty processors that the system can guarantee to identify, which plays an important role in measuring of the reliability of multiprocessor systems. In the work of Peng et al. in 2012, they proposed a new measure for fault diagnosis of systems, namely,$g$-good-neighbor conditional diagnosability. It is defined as the diagnosability of a multiprocessor system under the assumption that every fault-free node contains at least$g$fault-free neighbors, which can measure the reliability of interconnection networks in heterogeneous environments more accurately than traditional diagnosability. The$k$-ary$n$-cube is a family of popular networks. In this study, we first investigate and determine the$R_g$-connectivity of$k$-ary$n$-cube for$0\le g\le n.$Based on this, we determine the$g$-good-neighbor conditional diagnosability of$k$-ary$n$-cube under the PMC model and MM* model for$k\ge 4, n\ge 3$and$0\le g\le n.$Our study shows the$g$-good-neighbor conditional diagnosability of$k$-ary$n$-cube is several times larger than the classical diagnosability of$k$-ary$n$-cube.

Fault-tolerance plays an important role in improving the reliability of multiple earth-observing satellites, especially in emergent scenarios such as obtaining photographs on battlefields or earthquake areas. Fault tolerance can be implemented through scheduling approaches. Unfortunately, little attention has been paid to fault-tolerant scheduling on satellites. To address this issue, we propose a novel dynamic fault-tolerant scheduling model for real-time tasks running on multiple observation satellites. In this model, the primary-backup policy is employed to tolerate one satellite's permanent failure at one time instant. In the light of the fault-tolerant model, we develop a novel fault-tolerant satellite scheduling algorithm named FTSS. To improve the resource utilization, we apply the overlapping technology that includes primary-backup copy overlapping (i.e., PB overlapping) and backup-backup copy overlapping (i.e., BB overlapping). According to the satellites characterized with time windows for observations, we extensively analyze the overlapping mechanism on satellites. We integrate the overlapping mechanism with FTSS, which employs the task merging strategies including primary-backup copy merging (i.e., PB merging), backup-backup copy merging (i.e., BB merging) and primary-primary copy merging (i.e., PP merging). These merging strategies are used to decrease the number of tasks required to be executed, thereby enhancing system schedulability. To demonstrate the superiority of our FTSS, we conduct extensive experiments using the real-world satellite parameters supplied from the satellite tool kit or STK; we compare FTSS with the three baseline algorithms, namely, NMFTSS, NOFTSS, and NMNOFTSS. The experimental results indicate that FTSS efficiently improves the scheduling quality of others and is suitable for fault-tolerant satellite scheduling.

This paper presents a novel optimal location selection problem, which can be applied to a wide range of applications.After providing a formal definition of the novel query type, we explore an intuitive approach that sequentially scans all possible object combinations in the search space.Then, we propose an Overlapping Voronoi Diagram (OVD) model that defines OVDs and Minimum OVDs, and construct an algebraic structure under an OVD overlap operation.Based on the OVD model, we design an advanced approach to answer the query.Due to the high complexity of Voronoi diagram overlap computation, we improve the overlap operation by replacing the real boundaries of Voronoi diagrams with their Minimum Bounding Rectangles (MBR).We also propose a cost-bound iterative approach that efficiently processes a large number of Fermat-Weber problems.Our experimental results show that the proposed algorithms can evaluate the novel query type effectively and efficiently.

Fault-tolerant scheduling is an efficient approach to improving the reliability of multiple earth-observing satellites especially in some emergent scenarios such as obtaining photographs on battlefields or earthquake areas. Unfortunately, little work has been done to deal with the fault-tolerant scheduling on satellites. To address this issue, this paper presents a novel dynamic fault-tolerant scheduling model using primary-backup policy to tolerate one satellite's permanent failure at one time instant. On this basis, we propose a novel fault-tolerant satellite scheduling algorithm named FTSS, in which an overlapping technology is adopted to improve the resource utilization. Besides, the FTSS employs the task merging strategies to further enhance the schedulability. To demonstrate the superiority of our FTSS, we conduct extensive experiments by simulations using real-world satellite parameters from STK to compare FTSS with other baseline algorithms. The experimental results indicate that FTSS efficiently improves the scheduling quality of others and is suitable for fault-tolerant satellite scheduling.

Data deduplication techniques improve cost efficiency by dramatically reducing space needs of storage systems. SSD-based data cache has been adopted to remedy the declining I/O performance induced by deduplication operations in the latency-sensitive primary storage. Unfortunately, frequent data updates caused by classical cache algorithms (e.g., FIFO, LRU, and LFU) inevitably slow down SSDs' I/O processing speed while significantly shortening SSDs' lifetime. To address this problem, we propose a new approach-PLC-Cache-to greatly improve the I/O performance as well as write durability of SSDs. PLC-Cache is conducive to amplifying the proportion of the Popular and Long-term Cached (PLC) data, which is infrequently written and kept in SSD cache in a long time period to catalyze cache hits, in an entire SSD written data set. PLC-Cache advocates a two-phase approach. First, non-popular data are ruled out from being written into SSDs. Second, PLC-Cache makes an effort to convert SSD written data into PLC-data as much as possible. Our experimental results based on a practical deduplication system indicate that compared with the existing caching schemes, PLC-Cache shortens data access latency by an average of 23.4%. Importantly, PLC-Cache improves the lifetime of SSD-based caches by reducing the amount of data written to SSDs by a factor of 15.7.

Performance and energy consumption of a solid state disk (SSD) highly depend on file systems and I/O schedulers in operating systems. To find an optimal combination of a file system and an I/O scheduler for SSDs, we use a metric called the aggregative indicator (AI), which is the ratio of SSD performance value (e.g., data transfer rate in MB/s or throughput in IOPS) to that of energy consumption for an SSD. This metric aims to evaluate SSD performance per energy consumption and to study the SSD which delivers high performance at low energy consumption in a combination of a file system and an I/O scheduler. We also propose a metric called Cemp to study the changes of energy consumption and mean performance for an Intel SSD (SSD-I) when it provides the largest AI, lowest power, and highest performance, respectively. Using Cemp, we attempt to find the combination of a file system and an I/O scheduler to make SSD-I deliver a smooth change in energy consumption. We employ Filebench as a workload generator to simulate a wide range of workloads (i.e., varmail, fileserver, and webserver), and explore optimal combinations of file systems and I/O schedulers (i.e., optimal values of AI) for tested SSDs under different workloads. Experimental results reveal that the proposed aggregative indicator is comprehensive for exploring the optimal combination of a file system and an I/O scheduler for SSDs, compared with an individual metric.

In this paper, we propose a multi-level fault-tolerant storage cluster called MFTS, which provides flexible reliability for a wide variety of applications. MFTS makes use of a reliability upper-bound (i.e., Parameter r) to guide the process of adjusting fault-tolerance levels, i.e., i-erasure(s) and i {1, 2, .. ., r}. In particular, MFTS can map an appropriate coding scheme to an application with individual reliability requirements. MFTS is capable of partitioning multi-level reliable storage using a virtual storage space, thereby adapting to any changing reliability demands of applications. We present the implementation of the MFTS system, which adopts an intersecting zigzag sets code (IZS code) rather than replication or general-purpose erasure codes. Our MFTS has three salient features: partial updates, fast reconstructions, and minimal overhead of fault-tolerance level transitions. To quantify performance optimization in our storage cluster, we compare IZS-enabled MFTS with two storage clusters equipped with the Vandermondeand Cauchy-Reed-Solomon codes. The experimental results show that: 1) three schemes have comparable user-response-time performance in both the operational and degraded modes; 2) MFTS outperforms the other two alternatives by up to 26.1 percent in the offline reconstruction case; 3) MFTS speeds up the online reconstruction by up to 23.7 percent over the other two schemes with marginal increase in user response time.

The Popular Disk Concentration (PDC) technique and the Massive Array of Idle Disks (MAID) technique are two effective energy conservation schemes for parallel disk systems. The goal of PDC and MAID is to skew I/O load toward a few disks so that other disks can be transitioned to low power states to conserve energy. I/O load skewing techniques like PDC and MAID inherently affect reliability of parallel disks, because disks storing popular data tend to have high failure rates than disks storing cold data. To study reliability impacts of energy-saving techniques on parallel disk systems, we develop a mathematical modeling framework called MINT. We first model the behaviors of parallel disks coupled with power management optimization policies. We make use of data access patterns as input parameters to estimate each disk's utilization and power-state transitions. Then, we derive each disk's reliability in terms of annual failure rate from the disk's utilization, age, operating temperature, and power-state transition frequency. Next, we calculate the reliability of PDC and MAID parallel disk systems in accordance with the annual failure rate of each disk in the systems. Finally, we use real-world trace to validate out MINT model. Validation result shows that the behaviors of PDC and MAID which are modeled by MINT have a similar trend as that in the real-world.

RAID-6 is widely used to tolerate concurrent failures of any two disks in both disk arrays and storage clusters. Numerous erasure codes have been developed to implement RAID-6, of which MDS Codes are popular. Due to the limitation of parity generating schemes used in MDS codes, RAID-6-based storage systems suffer from low reconstruction performance. To address this issue, we propose a new class of XOR-based RAID-6 code (i.e., V2-Code), which delivers better reconstruction performance than the MDS RAID-6 code at low storage efficiency cost. V2-Code, a very simple yet flexible Non-MDS vertical code, can be easily implemented in storage systems. V2-Code's unique features include (1) lowest density, (2) steady length of parity chain, and (3) well balanced computation. We perform theoretical analysis and evaluation of the coding scheme under various configurations. The results show that V2-Code is a well-established RAID-6 code that outperforms both X-Code and Code-M in terms of reconstruction time. V2-Code can speed up the reconstruction time of X-Code by a factor of up to 3.31 and 1.79 under single disk failure and double disk failures, respectively.

An increasing number of spatial keyword query techniques that return qualified objects based on a comprehensive consideration of spatial and keyword constraints have been presented in the literature. Due to the complexity of the solutions to spatial keyword queries, systems that can effectively demonstrate the mechanisms will attract interest from the spatial database research community. However, very limited visualization systems have been developed for illustrating spatial keyword query evaluation. In this demonstration, we present a system that visualizes advanced solutions to efficiently answer the Spatial Keyword k Nearest Neighbor (SKkNN) query. With the two-level data management method and the friendly user interface implemented by the Standard Widget Toolkit (SWT) and Open Graphics Library (OpenGL), our system is able to not only interact with users in diverse manners, visualize datasets, and display the SKkNN query evaluation process, but it also helps users better understand the solutions in a more intuitive way.

Write amplification brings endurance challenges to NAND Flash-based solid state disks (SSDs) such as impacts upon their write endurance and lifetime. A large write amplification degrades program/erase cycles (P/Es) of NAND Flashes and reduces the endurance and performance of SSDs. The write amplification problem is mainly triggered by garbage collections, wear-leveling, metadata updates, and mapping table updates. Write amplification is defined as the ratio of data volume written by an SSD controller to data volume written by a host. In this paper, we propose a four-level model of write amplification for SSDs. The four levels considered in our model include the channel level, chip level, die level, and plane level. In light of this model, we design a method of analyzing write amplification of SSDs to trace SSD endurance and performance by incorporating the Ready/Busy (R/B) signal of NAND Flash. Our practical approach aims to measure the value of write amplification for an entire SSD rather than NAND Flashes. To validate our measurement technique and model, we implement a verified SSD (vSSD) system and perform a cross-comparison on a set of SSDs, which are stressed by micro-benchmarks and I/O traces. A new method for SSDs is adopted in our measurements to study the R/B signals of NAND Flashes in an SSD. Experimental results show that our model is accurate and the measurement technique is generally applicable to any SSDs.

Numerous geographic information system applications need to retrieve spatial objects which bear user specified keywords close to a given location. In this research, we present efficient approaches to answer spatial keyword queries on spatial networks. In particular, we formally introduce definitions of Spatial Keyword k Nearest Neighbor (SKkNN) and Spatial Keyword Range (SKR) queries. Then, we present a framework of a spatial keyword query evaluation system which is comprised of Keyword Constraint Filter (KCF), Keyword and Spatial Refinement (KSR), and the spatial keyword ranker. KCF employs an inverted index to calculate keyword relevancy of spatial objects, and KSR refines intermediate results by considering both spatial and keyword constraints with the spatial keyword ranker. In addition, we design novel algorithms for evaluating SKkNN and SKR queries. These algorithms employ the inverted index technique, shortest path search algorithms, and network Voronoi diagrams. Our extensive simulations show that the proposed SKkNN and SKR algorithms can answer spatial keyword queries effectively and efficiently.

In this paper, we present thermal-aware file assignment technique called TIGER for reducing cooling cost of storage clusters in data centers. TIGER first calculates the thresholds of disks in each node based on its contribution to heat recirculation in a data center. Next, TIGER assigns files to data nodes according to calculated thresholds. We evaluated performance of TIGER in terms of both cooling energy conservation and response time of a storage cluster. Our results confirm that TIGER reduces cooling-power requirements for clusters by offering about 10 to 15 percent cooling energy savings without significantly degrading I/O performance.

This paper presents a novel Predictive Energy-Aware Management (PEAM) system that is able to reduce the energy costs of storage systems by appropriately selecting data transmission methods. In particular, we evaluate the energy costs of three methods (1. transfer data without archiving and compression, 2. archive and transfer data, 3. compress and transfer data) in preliminary experiments. According to the results, we observe that the energy consumption of data transmission greatly varies case by case. We cannot simply apply one method in all cases. Therefore, we design an energy prediction model that can estimate the total energy cost of data transmission by using particular transmission methods. Based on the model, our predictive energy-aware management system can automatically select the most energy efficient method for data transmission. Our experimental results show that our system performs better than simply selecting any one among the three methods for data transmission in terms of energy efficiency.

Energy cost becomes a major part of data center operational cost. Computer system consume more power when it runs under high workload. Many past studies focused on how to predict power consumption by performance counters. Some models retrieve performance counters from chips. Some models query performance counters from OS. Most of these researches were verified on several machines and claimed their models were accurate under the test. We found different servers have different energy consumption characters even with same CPU. In this paper, we present BFEPM, a best fit energy prediction model. It choose best model based on the power consumption benchmark result. We illustrate how to use benchmark result to find a best fit model. Then we validate the viability and effectiveness of model on all published results. At last, we apply the best fit model on two different machines to estimate the real-time energy consumption. The results show our model can get better results than single model.

We present a power-efficient scheme for erasure-coded storage clusters---ECS2---which aims to offer high energy efficiency with marginal reliability degradation. ECS2utilizes data redundancies and deferred writes to conserve energy. In ECS2parity blocks are buffered exclusively in active data nodes whereas parity nodes are placed into low-power mode. (k+r, k) RS-coded ECS2can achieve ⌈(r+ 1)/2⌉-fault tolerance forkactive data nodes andr-fault tolerance for allk+rnodes. ECS2employs the following three optimizing approaches to improve the energy efficiency of storage clusters. (1) An adaptive threshold policy takes system configurations and I/O workloads into account to maximize standby time periods; (2) a selective activation policy minimizes the number of power-transitions in storage nodes; and (3) a region-based buffer policy speeds up the synchronization process by migrating parity blocks in a batch method. After implementing an ECS2-based prototype in a Linux cluster, we evaluated its energy efficiency and performance using four different types of I/O workloads. The experimental results indicate that compared to energy-oblivious erasure-coded storage, ECS2can save the energy used by storage clusters up to 29.8% and 28.0% in read-intensive and write-dominated workloads when k = 6 and r = 3, respectively. The results also show that ECS2accomplishes high power efficiency in both normal and failed cases without noticeably affecting the I/O performance of storage clusters.

We present a multicore-enabled smart storage for clusters in general and MapReduce clusters in particular. The goal of this research is to improve performance of data-intensive parallel applications on clusters by offloading data processing to multicore processors in storage nodes. Compared with traditional storage devices, next-generation disks will have computing capability to reduce computational load of host processors or CPUs. With the advance of processor and memory technologies, smart storage systems are promising devices to perform complex on-disk operations. The proposed smart storage system can avoid moving a huge amount of data back and forth between storage nodes and computing nodes in a cluster. To enhance the performance of data-intensive applications, we have designed a smart storage system called Multicore-enabled Smart Storage (McSD), in which a multicore processor is integrated in storage nodes. We have implemented a programming framework for data-intensive applications running on a computing system coupled with McSD. The programming framework aims at balancing load between computing nodes and multicore-enabled smart storage nodes. To fully utilize multicore processors in smart storage nodes, we have implemented the MapReduce model for McSDs to handle parallel computing on a cluster. A prototype of McSD has been implemented in a cluster connected by Gigabit Ethernet. Experimental results show that McSD can significantly reduce the execution times of three real-world applications - word count, string matching, and matrix multiplication. We demonstrate that the integration of multicore-enabled smart storage with MapReduce clusters is a promising approach to improving overall performance of data-intensive applications on clusters.

Recognizing that power and cooling cost for data centers are increasing, we address in this study the thermal impact of storage systems. In the first phase of this work, we generate the thermal profile of a storage server containing three hard disks. The profiling results show that disks have comparable thermal impacts as processing and networking elements to overall storage node temperature. We develop a thermal model to estimate the outlet temperature of a storage server based on processor and disk utilizations. The thermal model is validated against data acquired by an infrared thermometer as well as build-in temperature sensors on disks. Next, we apply the thermal model to investigate the thermal impact of workload management on storage systems. Our study suggests that disk-aware thermal management techniques have significant impacts on reducing cooling cost of storage systems. We further show that this work can be extended to analysis the cooling cost of data centers with massive storage capacity.

Online content distribution systems, which store incredibly large amounts of information and provide service to large numbers of users, are becoming increasingly commonplace. To fulfill the wide range of requests sent by different users, these systems must ensure efficient handling of massive amount of data. To achieve this goal, the in-depth analysis and comprehensive understanding of user behaviors are critical. However, analyzing the behaviors of worldwide users with different needs is a very challenging task. This is especially true when historical user behaviors evolve over time or may be affected by unpredictable events. In this paper, we present a number of workload characterization techniques applied to one of the world's largest online satellite image distribution systems operated by the U.S. Geological Survey (USGS) and NASA.

Most researches of Solid State Drives (SSDs) architectures rely on Flash Translation Layer (FTL) algorithms and wear-leveling; however, internal parallelism in Solid State Drives has not been well explored. In this research, we proposed a new strategy to improve SSD write performance by enhancing internal parallelism inside SSDs. A SDRAM buffer is added in the design for buffering and scheduling write requests. Because the same logical block numbers may be translated to different physical numbers at different times in FTL, the on-board SDRAM buffer is used to buffer requests at the lower level of FTL. When the buffer is full, same amount of data will be assigned to each storage package in SSDs to enhance internal parallelism. To accurately evaluate performance, we use both synthetic workloads and real-world applications in experiments. We compare the enhanced internal parallelism scheme with the traditional LRU strategy since it is unfair to compare an SSD having buffer with an SSD without a buffer. The simulation results demonstrate that the writing performance of our design is significantly improved compared with the LRU-cache strategy with the same amount of buffer sizes.

This paper presents an offloading framework - ORCA - to map I/O-intensive code to a cluster that consists of computing and storage nodes. To reduce data transmission among computing and storage nodes. our offloading framework partitions and schedules CPU-bound and I/O-bound modules to computing nodes and active storage nodes, respectively. From developer's perspective, ORCA helps them to deal with execution-path control, offloading executable code, and data sharing over a network. Powered by the offloading APIs, developers without any I/O offloading or network programming experience are allowed to write new I/O-intensive code running efficiently on clusters. We implement the ORCA framework on a cluster to quantitatively evaluate performance improvements offered by our approach. We run five real-world applications on both homogeneous and heterogeneous computing environments. Experimental results show ORCA speeds up the performance of all the five tested applications by a factor of up to 90.1% with an average of 75.5%. Moreover, the results confirm that ORCA reduces network burden imposed by I/O-intensive applications by a factor of anywhere between 35 to 68.

Caching is widely known to be an effective method for improving I/O performance by storing frequently used data on higher speed storage components. However, most existing studies that focus on caching performance evaluate fairly small files populating a relatively small cache. Few reports are available that detail the performance of traditional cache replacement policies on extremely large caches. Do such traditional caching policies still work effectively when applied to systems with petabytes of data? In this paper, we comprehensively evaluate the performance of several cache policies, which include First-In-First-Out (FIFO), Least Recently Used (LRU) and Least Frequently Used (LFU), on the global satellite imagery distribution application maintained by the U.S. Geological Survey (USGS) Earth Resources Observation and Science Center (EROS). Evidence is presented suggesting traditional caching policies are capable of providing performance gains when applied to large data sets as with smaller data sets. Our evaluation is based on approximately three million real-world satellite images download requests representing global user download behavior since October 2008.

In this paper, we present an informed prefetching technique called IPODS that makes use of application-disclosed access patterns to prefetch hinted blocks in distributed multi-level storage systems. We develop a prefetching pipeline in IPODS, where an informed prefetching process is divided into a set of independent prefetching steps among multiple storage levels in a distributed system. In the IPODS system, while data blocks are prefetched from hard disks to memory buffers in remote storage servers, data blocks buffered in the servers are prefetched through networks to clients' local cache. We show that these two prefetching steps can be handled in a pipelining manner to improve I/O performance of distributed storage systems. Our IPODS technique differs itself from existing prefetching schemes in two ways. First, IPODS reduces applications' I/O stalls by keeping hinted data in clients' local caches and storage servers' fast buffers (e.g., solid state disks). Second, in a prefetching pipeline, multiple informed prefetching mechanisms semi-dependently coordinate to fetch blocks (1) from low-level (slow) to high-level (fast) storage devices in servers and (2) from high-level devices in servers to clients' local cache. The prefetching pipeline in IPODS judiciously hides network latencies in distributed storage systems, thereby reducing the overall I/O access time in distributed systems. Using a wide range of real-world I/O traces, our experiments show that IPODS can improve noticeably I/O performance of distributed storage systems.

An efficient resource management mechanism is important in a heterogeneous system to discover available resources, to allocate an appropriate subset of resources to applications, and to map data or tasks onto selected resources. The key component, tasks scheduling, draws our attention. Make span is the principal concern many existing researches. But, other QoS requirements are also important in more and more realistic applications. Like Grid service it is expected that the service provider be reliable, robust, or highly available. In this study, an existing availability-aware scheduling model called SSAC is investigated first. Then, we proposed an optimization approach to increase the availability and to reduce the make span of tasks running in heterogeneous systems. Three quantitative conditions are used to guide the optimization. Our experimental results show that compared with three existing solutions (Minmin, SSAC and ACO), our algorithm significantly improves the availability and performance of multiclass tasks running in heterogeneous systems.

An increasing number of commodity clusters are connected to each other by public networks, which have become a potential threat to security sensitive parallel applications running on the clusters. To address this security issue, we developed a Message Passing Interface (MPI) implementation to preserve confidentiality of messages communicated among nodes of clusters in an unsecured network. We focus on M PI rather than other protocols, because M PI is one of the most popular communication protocols for parallel computing on clusters. Our MPI implementation-called ES-MPICH2-was built based on MPICH2 developed by the Argonne National Laboratory. Like MPICH2, ES-MPICH2 aims at supporting a large variety of computation and communication platforms like commodity clusters and high-speed networks. We integrated encryption and decryption algorithms into the MPICH2 library with the standard MPI interface and; thus, data confidentiality of MPI applications can be readily preserved without a need to change the source codes of the MPI applications. MPI-application programmers can fully configure any confidentiality services in MPICHI2, because a secured configuration file in ES-MPICH2 offers the programmers flexibility in choosing any cryptographic schemes and keys seamlessly incorporated in ES-MPICH2. We used the Sandia Micro Benchmark and Intel MPI Benchmark suites to evaluate and compare the performance of ES-MPICH2 with the original MPICH2 version. Our experiments show that overhead incurred by the confidentiality services in ES-MPICH2 is marginal for small messages. The security overhead in ES-MPICH2 becomes more pronounced with larger messages. Our results also show that security overhead can be significantly reduced in ES-MPICH2 by high-performance clusters. The executable binaries and source code of the ES-MPICH2 implementation are freely available at http:// www.eng.auburn.edu/~xqin/software/es-mpich2/.

Reducing energy consumption has been an important design issue for large-scale streaming media storage systems. Existing energy conservation techniques are inadequate to achieve high energy efficiency for streaming media computing environments due to high data migration overhead. To address this problem, we propose in this paper a new energy-efficient method called Explicit Energy Saving Disk Cooling or EESDC. EESDC significantly reduces data migration overhead because of two reasons. First, a set of disks referred to Explicit Energy Saving Disks (EESD) is explicitly fixed according to temporal system load. Second, all the migrated data in EESDC directly contribute on extending the idle time of EESD to conserve more energy efficiently. Therefore, the EESDC method is conducive to saving more energy by quickly achieving energy-efficient data layouts without unnecessary data migrations. We implement EESDC in a simulated disk system, which is validated against a prototype system powered by our EESDC. Our experimental results using both real-world traces and synthetic traces show that EESDC can save up to 28.13-29.33 percent energy consumption for typical streaming media traces. Energy efficiency of streaming media storage systems can be improved by 3.3-6.0 times when EESDC is coupled.

We develop a mathematical model - MREED - to quantitatively evaluate the failure rate of energy-efficient parallel storage systems. The Power-Aware Redundant Array of Inexpensive Disk (PARAID) aims to reduce energy use of commodity server-class disks without specialized hardware. The goal of PARAID is to skewed striping pattern to adapt to the system load by changing the number of powered disks. By spinning down disks during light workloads, PARAID can reduce power consumption, while still meeting performance demands. We show that MREED can be used to estimate a five-disk PARAID-0 system. We validate the accuracy of MREED using the DiskSim simulator. Our approach shows that MREED can rely on file access pattern to estimate system utilization correctly. Furthermore, even thought PARAID may achieve reasonable reliability, our model shows that PARAID's reliability is affected by data locality.

Performance improvement and energy conservation are two conflicting objectives in large scale parallel storage systems. In this paper, we propose a novel solution to achieve the twin objectives of maximizing performance and minimizing energy consumption of parallel storage systems. Specifically, a buffer-disk based architecture (BUD for short) is designed to conserve energy. A heat-based dynamic data caching strategy is developed to improve performance. The BUD architecture strives to allocate as many requests as possible to buffer disks, thereby keeping a large number of idle data disks in low-power states. This can provide significant opportunities for energy conservation while making buffer disks a potential performance bottleneck. The heat-based data caching strategy aims to achieve good load balancing in buffer disks and alleviate overall performance degradation caused by unbalanced workload. Our experimental results have shown that the proposed BUD framework and dynamic data caching strategy are able to conserve energy by 84.4% for small reads and 78.8% for large reads with slightly degraded response time.

There is a growing demand for large-scale distributed storage systems to support resource sharing and fault tolerance. Although heterogeneity issues of distributed systems have been widely investigated, little attention has yet been paid to security solutions designed for distributed storage systems with heterogeneous vulnerabilities. This fact motivates us to investigate a fragment allocation scheme called S-FAS to improve security of a distributed system where storage sites have a wide variety of vulnerabilities. In the S-FAS approach, we integrate file fragmentation with the secret sharing technique in a distributed storage system with heterogeneous vulnerabilities. Storage sites in a distributed systems are classified into a variety of different server types based on vulnerability characteristics. Given a file and a distributed system, S-FAS allocates fragments of the file to as many different types of nodes as possible in the system. Data confidentiality is preserved because fragments of a file are allocated to multiple storage nodes. We develop storage assurance and dynamic assurance models to evaluate the quality of security offered by S-FAS. Analysis results show that fragment allocations made by S-FAS lead to enhanced security because of the consideration of heterogeneous vulnerabilities in distributed storage systems.

Fault-tolerant scheduling plays a significant role in improving system reliability of clusters. Although extensive fault-tolerant scheduling algorithms have been proposed for real-time tasks in parallel and distributed systems, quality of service (QoS) requirements of tasks have not been taken into account. This paper presents a fault-tolerant scheduling algorithm called QAFT that can tolerate one node's permanent failures at one time instant for real-time tasks with QoS needs on heterogeneous clusters. In order to improve system flexibility, reliability, schedulability, and resource utilization, QAFT strives to either advance the start time of primary copies and delay the start time of backup copies in order to help backup copies adopt the passive execution scheme, or to decrease the simultaneous execution time of the primary and backup copies of a task as much as possible to improve resource utilization. QAFT is capable of adaptively adjusting the QoS levels of tasks and the execution schemes of backup copies to attain high system flexibility. Furthermore, we employ the overlapping technology of backup copies. The latest start time of backup copies and their constraints are analyzed and discussed. We conduct extensive experiments to compare our QAFT with two existing schemes-NOQAFT and DYFARS. Experimental results show that QAFT significantly improves the scheduling quality of NOQAFT and DYFARS.

High-performance clusters have been widely deployed to solve challenging and rigorous scientific and engineering tasks. On one hand, high performance is certainly an important consideration in designing clusters to run parallel applications. On the other hand, the ever increasing energy cost requires us to effectively conserve energy in clusters. To achieve the goal of optimizing both performance and energy efficiency in clusters, in this paper, we propose two energy-efficient duplication-based scheduling algorithms-Energy-Aware Duplication (EAD) scheduling and Performance-Energy Balanced Duplication (PEBD) scheduling. Existing duplication-based scheduling algorithms replicate all possible tasks to shorten schedule length without reducing energy consumption caused by duplication. Our algorithms, in contrast, strive to balance schedule lengths and energy savings by judiciously replicating predecessors of a task if the duplication can aid in performance without degrading energy efficiency. To illustrate the effectiveness of EAD and PEBD, we compare them with a nonduplication algorithm, a traditional duplication-based algorithm, and the dynamic voltage scaling (DVS) algorithm. Extensive experimental results using both synthetic benchmarks and real-world applications demonstrate that our algorithms can effectively save energy with marginal performance degradation.

A critical problem with parallel I/O systems is the fact that disks consume a significant amount of energy. To design economically attractive and environmentally friendly parallel I/O systems, we propose an energy-aware prefetching strategy (PRE-BUD) for parallel I/O systems with disk buffers. We introduce a new architecture that provides significant energy savings for parallel I/O systems using buffer disks while maintaining high performance. There are two buffer disk configurations: (1) adding an extra buffer disk to accommodate prefetched data, and (2) utilizing an existing disk as the buffer disk. PRE-BUD is not only able to reduce the number of power-state transitions, but also to increase the length and number of standby periods. As such, PRE-BUD conserves energy by keeping data disks in the standby state for increased periods of time. Compared with the first prefetching configuration, the second configuration lowers the capacity of the parallel disk system. However, the second configuration is more cost-effective and energy-efficient than the first one. Finally, we quantitatively compare PRE-BUD with both disk configurations against three existing strategies. Empirical results show that PRE-BUD is able to reduce energy dissipation in parallel disk systems by up to 50 percent when compared against a non-energy aware approach. Similarly, our strategy is capable of conserving up to 30 percent energy when compared to the dynamic power management technique.

Reducing power consumption of wireless networks has become a major goal in designing modern multimedia wireless systems. In an effort to reduce power consumption, this paper addresses the issue of scheduling real-time messages in multimedia wireless networks subject to both timing and power constraints. A power-consumption model is introduced to calculate power-consumption rates in accordance with message-transmission rates. Next, a new message-scheduling scheme called Power-aware Real-time Message (PARM) is developed to generate message-transmission schedules that minimize power consumption of multimedia wireless-network interfaces and the probability of missing deadlines for real-time messages. With a power-aware scheduling policy in place, the proposed PARM scheme is very energy-efficient. Experimental results based on a wide variety of synthetic workloads and eight real-world applications show that PARM significantly reduces energy dissipation while maintaining low missed rates. PARM reduces power consumption of data transmissions by up to 99.4% (with an average of 86.7%) for synthetic network traffic and saves energy by up to 60.0% (with an average of 34.1%) in the eight real-world applications.

Improving energy efficiency of mass storage systems has become an important and pressing research issue in large HPC centers and data centers. New energy conservation techniques in storage systems constantly spring up; however, there is a lack of systematic and uniform way of accurately evaluating energy-efficient storage systems and objectively comparing a wide range of energy-saving techniques. This research presents a new integrated scheme, called TRACER, for evaluating energy-efficiency of mass storage systems and judging energy-saving techniques. The TRACER scheme consists of a toolkit used to measure energy efficiency of storage systems as well as performance and energy metrics. In addition, TRACER contains a novel and accurate workload-control module to acquire power varying with workload modes and I/O load intensity. The workload generator in TRACER facilitates a block-level trace replay mechanism. The main goal of the workload-control module is to select a certain percentage (e.g., anywhere from 10% to 100%) of trace entries from a real-world I/O trace file uniformly and to replay filtered trace entries to reach any level of I/O load intensity. TRACER is experimentally validated on a general RAID5 enterprise disk array. Our experiments demonstrate that energy-efficient mass storage systems can be accurately evaluated on full scales by TRACER. We applied TRACER to investigate impacts of workload modes and load intensity on energy-efficiency of storage devices. This work shows that TRACER can enable storage system developers to evaluate energy efficiency designs for storage systems.

Compared to traditional wireless network routing protocols, geographic routing provides superior scalability and thus is widely used in vehicular ad hoc networks (VANETs). However, it requires every vehicle to broadcast its location information to its neighboring nodes, and this process will compromise user's location privacy. Existing solutions to this problem can be categorized into two groups: 1) hiding user's location or 2) preserving user's identification information in routing protocols, which drastically reduce network performances. To address this issue, we proposed a dummy-based location privacy protection (DBLPP) routing protocol, in which routing decision is made based upon the dummy distance to the destination (DOD), instead of users' true locations. In this scheme, users' true locations and identification information are preserved, so the user's location privacy is protected. Compared to existing solutions, simulation results show that while DBLPP provides similar network performances as other routing protocols, it achieves a higher level of location privacy protection on vehicles in networks.

Improving security and minimizing power consumption are crucial for large-scale data storage systems. Although a handful of studies have been focused on data security and energy efficiency, most of the existing approaches have concentrated on only one of these two metrics. In this paper, we present a new approach to integrating power optimization with security services to enhance the security of energy-efficient large-scale storage systems. In our approach, we make use of the dynamic speed control for power management technique, or DRPM, to conserve energy in secure storage systems. In this study we develop two ways of integrating confidentiality services with the dynamic disk speed control technique. The first strategy - security aggressive in nature - is focused on the improvement of storage system security with less emphasis on energy conservation. The second strategy gives higher priority to energy conservation as opposed to the security optimization. Our experimental results show that the energy-aggressive approach provides better energy savings than the security-aggressive approach. However, the quality of security achieved by the security-aggressive scheme is higher than that of the energy-aggressive approach. Moreover, the empirical results show that energy savings yielded by the two approaches become more pronounced when the data size is increased. The findings illustrate that the response time of the security-aggressive approach is more sensitive to data size than that of the energy-aggressive scheme.

Energy efficient computing is becoming increasingly important as the scale of parallel computing systems is expanding. As the processing power of parallel computing systems has been incremented there has been an increased demand for large scale storage systems to store the output of these parallel computing systems. Data centers are growing at an enormous pace and it is important to investigate a means of managing the energy efficiency of large scale parallel storage systems. To address these issues we introduce EEVFS (Energy Efficient Virtual File System), which is able to manage data placement and disk states to help improve the energy efficiency of a parallel disk system. EEVFS places data on the storage disks in an energy efficient layout and attempts to predict when each disk will be idle for a large period of time, facilitating a state transition into the standby state. EEVFS should also maintain relatively high performance, so we have built a load balancing policy into the data partitioning of EEVFS. The implementation architecture and measured results are presented to demonstrate the energy efficiency and performance characteristics of EEVFS.

Steady improvements in storage capacities and CPU clock speeds intensify the performance bottleneck at the I/O subsystem of modern computers. Caching data can efficiently short circuit costly delays associated with disk accesses. Recent studies have shown that disk I/O performance gains provided by a cache buffer do not scale with cache size. Therefore, new algorithms have to be investigated to better utilize cache buffer space. Predictive prefetching and caching solutions have been shown to improve I/O performance in an efficient and scalable manner in simulation experiments. However, most predictive prefetching algorithms have not yet been implemented in real-world storage systems due to two main limitations: first, the existing prefetching solutions are unable to self regulate based on changing I/O workload; second, excessive number of unneeded blocks are prefetched. Combined, these drawbacks make predictive prefetching and caching a less attractive solution than the simple LRU management. To address these problems, in this paper we propose an automatic prefetching and caching system (or APACS for short), which mitigates all of these shortcomings through three unique techniques, namely: (1) dynamic cache partitioning, (2) prefetch pipelining, and (3) prefetch buffer management. APACS dynamically partitions the buffer cache memory, used for prefetched and cached blocks, by automatically changing buffer/cache sizes in accordance to global I/O performance. The adaptive partitioning scheme implemented in APACS optimizes cache hit ratios, which subsequently accelerates application execution speeds. Experimental results obtained from trace-driven simulations show that APACS outperforms the LRU cache management and existing prefetching algorithms by an average of over 50%.

In largely distributed clusters, computing nodes are geographically deployed in various computing sites. Information processed in a distributed cluster is shared among a group of distributed processes or users by virtue of messages passing protocols (e.g. message passing interface - MPI) running on the Internet. Because of the open accessible nature of the Internet, data encryption for these large-scale distributed clusters becomes a non-trivial and challenging problem. To address this issue, we enhanced the security of the MPI (Message Passing Interface) protocol by encrypting and decrypting messages sent and received among computing nodes. In this study we focused on MPI rather than other protocols because MPI is one of the most popular communication protocols for cluster computing environments. From among a variety of MPI implementations, we picked MPICH2 developed by the Argonne National Laboratory. The design goal of MPICH2 - a widely used MPI implementation - is to combine portability with high performance. We integrated encryption algorithms into the MPICH2 library so that data confidentiality of MPI applications could be readily preserved without a need to change the source codes of the MPI applications. since we provide a security enhanced MPI-library with the standard MPI interfact, data communications of a conventional MPI program can be secured without converting the program into the corresponding secure version. We used Sandia Micro Benchmark and Intel MPI Benchmarks to evaluate and compared the performance of original MPICH2 and Enhanced Security MPICH2. According to the performance evaluation, ES-MPICH2 provides secured Message Passing Interface by sacrificing reasonable system performance.

Dynamic demands are the basic inputs of some existing dynamic assignment function. However, current data collection technologies do not directly support all the requirements of Dynamic Traffic Assignment (DTA) models. As a new traffic data collection technology, cell probe data could provide link flow, travel time and dynamic traffic demand at the same time. But these parameters are partial for a network.

Solid-state disks (SSDs) with high I/O performance are increasingly becoming popular. To extend the life time of flash memory, one can apply wear-leveling strategies to manage data blocks. However, wear-leveling strategies certainly inevitably degrade write performance. In addition to low write performance, wear-leveling strategies make one block unwritable when one bit of this block is invalid. Although data reconstruction techniques have been widely employed in disk arrays, the reconstruction techniques has not been studied in the context of solid-state disks. In this paper, we present a new fine-grained data-reconstruction algorithm for solid-state disks. The algorithm aims to provide a simple yet efficient wear-leveling strategy that improves both I/O performance and reliability of solid-state disks. Simulation experiments show that all data blocks have very similar in terms of erasure times. The number of extra erasures incurred by our algorithm is very marginal.

An infrastructure-as-a-service cloud system provides computational capacities to remote users. Parallel processing in the cloud system can shorten the execution of jobs. Parallel processing requires a mechanism to scheduling the executions order as well as resource allocation. Furthermore, a preemptable scheduling mechanism can improve the utilization of resources in clouds. In this paper, we present a preemptable job scheduling mechanism in cloud system. We propose two feedback dynamic scheduling algorithms for this scheduling mechanism. We compare these two scheduling algorithms in simulations. The results show that the feedback procedure in our algorithms works well in the situation where resource contentions are fierce.

Cluster computing has emerged as a primary and cost-effective platform for running parallel applications, including communication-intensive applications that transfer a large amount of data among the nodes of a cluster via the interconnection network. Conventional load balancers have proven effective in increasing the utilization of CPU, memory, and disk I/O resources in a cluster. However, most of the existing load-balancing schemes ignore network resources, leaving an opportunity to improve the effective bandwidth of networks on clusters running parallel applications. For this reason, we propose a communication-aware load-balancing technique that is capable of improving the performance of communication-intensive applications by increasing the effective utilization of networks in cluster environments. To facilitate the proposed load-balancing scheme, we introduce a behavior model for parallel applications with large requirements of network, CPU, memory, and disk I/O resources. Our load-balancing scheme can make full use of this model to quickly and accurately determine the load induced by a variety of parallel applications. Simulation results generated from a diverse set of both synthetic bulk synchronous and real parallel applications on a cluster show that our scheme significantly improves the performance, in terms of slowdown and turn-around time, over existing schemes by up to 206 percent (with an average of 74 percent) and 235 percent (with an average of 82 percent), respectively.

Energy conservation has become a critical problem for real-time embedded storage systems. Although a variety of approaches for reducing energy consumption have been extensively studied, energy conservation for real-time embedded storage systems is still an open problem. In this article, we propose an energy management strategy, I/O Burstiness for Energy Conservation (IBEC), exploiting the burstiness of real-time embedded storage systems applications. Our approach aims at combining the IBEC energy-management strategy with a Linux-based disk block-scheduling mechanism to conserve the energy of storage systems. Extensive experiments are conducted involving a number of synthetic disk traces as well as real-world data-intensive traces. To evaluate the energy efficiency of IBEC, we compare the performance of IBEC against three existing strategies, namely, PA-EDF, DP-EDF, and EDF. Compared with the alternative strategies, IBEC reduces the power consumption of real-time embedded disks system by up to 60%.

Many energy conservation techniques have been proposed to achieve high energy efficiency in disk systems. Unfortunately, growing evidence shows that energy-saving schemes in disk drives usually have negative impacts on storage systems. Existing reliability models are inadequate to estimate reliability of parallel disk systems equipped with energy conservation techniques. To solve this problem, we propose a mathematical model - called MINT - to evaluate the reliability of a parallel disk system where energy-saving mechanisms are implemented. In this paper, we focus on modeling the reliability impacts of two well-known energy-saving techniques - the Popular Disk Concentration technique (PDC) and the Massive Array of Idle Disks (MAID). We started this research by investigating how PDC and MAID affect the utilization and power-state transition frequency of each disk in a parallel disk system. We then model the annual failure rate of each disk as a function of the disk's utilization, power state transition frequency as well as operating temperature, because these parameters are key reliability-affecting factors in addition to disk ages. Next, the reliability of a parallel disk system can be derived from the annual failure rate of each disk in the parallel disk system. Finally, we used MINT to study the reliability of a parallel disk system equipped with the PDC and MAID techniques. Experimental results show that PDC is more reliable than MAID when disk workload is low. In contrast, the reliability of MAID is higher than that of PDC under relatively high I/O load.

In the past decade parallel disk systems have been highly scalable and able to alleviate the problem of disk I/O bottleneck, thereby being widely used to support a wide range of data-intensive applications. Optimizing energy consumption in parallel disk systems has strong impacts on the cost of backup power-generation and cooling equipment, because a significant fraction of the operation cost of data centres is incurred by energy consumption and cooling. Although flash memory is very energy-efficient compared to disk drives, flash memory is too expensive to use as a major component in large-scale storage systems. In other words, it is not a cost-effective way to make use of large flash memory to build energy-efficient storage systems. To address this problem, in this paper we proposed a hybrid disk architecture or HYBUD that integrates a non-volatile flash memory with buffer disks to build cost-effective and energy-efficient parallel disk systems. While the most popular data sets are cached in flash memory, the second most popular data sets can be stored and retrieved from buffer disks. HYBUD is energy efficient because flash memory coupled with buffer disks can serve a majority of incoming disk requests, thereby keeping a large number of other data disks in the low-power state for longer period times. Furthermore, HYBUD is cost-effective by the virtue of inexpensive buffer disks assisting flash memory to cache a huge amount of popular data. Experimental results demonstratively show that compared with two existing non-hybrid architectures, HYBUD provides significant energy savings for parallel disk systems in a very cost effective way.

In the past decade, parallel disk systems have been developed to address the problem of I/O performance. A critical challenge with modern parallel I/O systems is that parallel disks consume a significant amount of energy in servers and high performance computers. To conserve energy consumption in parallel I/O systems, one can immediately spin down disks when disk are idle; however, spinning down disks might not be able to produce energy savings due to penalties of spinning operations. Unlike powering up CPUs, spinning down and up disks need physical movements. Therefore, energy savings provided by spinning down operations must offset energy penalties of the disk spinning operations. To substantially reduce the penalties incurred by disk spinning operations, we developed a novel approach to conserving energy of parallel I/O systems with write buffer disks, which are used to accumulate small writes using a log file system. Data sets buffered in the log file system can be transferred to target data disks in a batch way. Thus, buffer disks aim to serve a majority of incoming write requests, attempting to reduce the large number of disk spinning operations by keeping data disks in standby for long period times. Interestingly, the write buffer disks not only can achieve high energy efficiency in parallel I/O systems, but also can shorten response times of write requests. To evaluate the performance and energy efficiency of our parallel I/O systems with buffer disks, we implemented a prototype using a cluster storage system as a testbed. Experimental results show that under light and moderate I/O load, buffer disks can be employed to significantly reduce energy dissipation in parallel I/O systems without adverse impacts on I/O performance.

Cluster storage systems are essential building blocks for many high-end computing infrastructures. Although energy conservation techniques have been intensively studied in the context of clusters and disk arrays, improving energy efficiency of cluster storage systems remains an open issue. To address this problem, we describe in this paper an approach to implementing an energy-efficient cluster storage system or ECOS for short. ECOS relies on the architecture of cluster storage systems in which each I/O node manages multiple disks - one buffer disk and several data disks. Given an I/O node, the key idea behind ECOS is to redirect disk requests from data disks to the buffer disk. To balance I/O load among I/O nodes, ECOS might redirect requests from one I/O node into the others. Redirecting requests is a driving force of energy saving, and the reason is two-fold. First, ECOS makes an effort to keep buffer disks active while placing data disks into standby in a long time period to conserve energy. Second, ECOS reduces the number of disk spin downs/ups in I/O nodes. The idea of ECOS was implemented in a Linux cluster, where each I/O node contains one buffer disk and two data disks. Experimental results show that ECOS improves the energy efficiency of traditional cluster storage systems where buffer disks are not employed. Adding one extra buffer disk into each I/O node seemingly has negative impact on energy saving. Interestingly, our results indicate that ECOS equipped with extra buffer disks is more energy efficient than the same cluster storage system without the buffer disks. The implication of the experiments is that using existing data disks in I/O nodes to perform as buffer disks can achieve even higher energy efficiency.

The Popular Disk Concentration (PDC) technique and the Massive Array of Idle Disks (MAID) technique are two effective energy saving schemes for parallel disk systems. The goal of PDC and MAID is to skew I/O load towards a few disks so that other disks can be transitioned to low power states to conserve energy. I/O load skewing techniques like PDC and MAID inherently affect reliability of parallel disks because disks storing popular data tend to have high failure rates than disks storing cold data. To achieve good tradeoffs between energy efficiency and disk reliability, we first present a reliability model to quantitatively study the reliability of energy-efficient parallel disk systems equipped with the PDC and MAID schemes. Then, we propose a novel strategy—disk swapping—to improve disk reliability by alternating disks storing hot data with disks holding cold data. We demonstrate that our disk-swapping strategies not only can increase the lifetime of cache disks in MAID-based parallel disk systems, but also can improve reliability of PDC-based parallel disk systems.

Improving energy efficiency of security-aware storage systems is challenging, because security and energy efficiency are often two conflicting goals. The first step toward making the best tradeoffs between high security and energy efficiency is to profile encryption algorithms to decide if storage systems would be able to produce energy savings for security mechanisms. We are focused on encryption algorithms rather than other types of security services, because encryption algorithms are usually computation-intensive. In this study, we used the XySSL libraries and profiled operations of several test problems using Conky - a lightweight system monitor that is highly configurable. Using our profiling techniques we concluded that although 3DES is much slower than AES encryption,it more likely to save energy in security-aware storage systems using 3DES than AES. The CPU is the bottleneck in 3DES, allowing us to take advantage of dynamic power management schemes to conserve energy at the disk level.After profiling several hash functions, we noticed that the CPU is not the bottleneck for any of these functions,indicating that it is difficult to leverage the dynamic power management technique to conserve energy of a single disk where hash functions are implemented for integrity checking.

Parallel disk systems consume a significant amount of energy due to the large number of disks. To design economically attractive and environmentally friendly parallel disk systems, in this paper we design and evaluate an energy-aware prefetching strategy for parallel disk systems consisting of a small number of buffer disks and large number of data disks. Using buffer disks to temporarily handle requests for data disks, we can keep data disks in the low-power mode as long as possible. Our prefetching algorithm aims to group many small idle periods in data disks to form large idle periods, which in turn allow data disks to remain in the standby state to save energy. To achieve this goal, we utilize buffer disks to aggressively fetch popular data from regular data disks into buffer disks, thereby putting data disks into the standby state for longer time intervals. A centrepiece in the prefetching mechanism is an energy-saving prediction model, based on which we implement the energy-saving calculation module that is invoked in the prefetching algorithm. We quantitatively compare our energy-aware prefetching mechanism against existing solutions, including the dynamic power management strategy. Experimental results confirm that the buffer-disk-based prefetching can significantly reduce energy consumption in parallel disk systems by up to 50 percent. In addition, we systematically investigate the energy efficiency impact that varying disk power parameters has on our prefetching algorithm.

An increasing number of real-time applications like railway signaling control systems and medical electronics systems require high quality of security to assure confidentiality and integrity of information. Therefore, it is desirable and essential to fulfill security requirements in security-critical real-time systems. This paper addresses the issue of optimizing quality of security in real-time systems. To meet the needs of a wide variety of security requirements imposed by real-time systems, a group-based security service model is used in which the security services are partitioned into several groups depending on security types. While services within the same security group provide the identical type of security service, the services in the group can achieve different quality of security. Security services from a number of groups can be combined to deliver better quality of security. In this study, we seamlessly integrate the group-based security model with a traditional real-time scheduling algorithm, namely earliest deadline first (EDF). Moreover, we design and develop a security-aware EDF schedulability test. Given a set of real-time tasks with chosen security services, our scheduling scheme aims at optimizing the combined security value of the selected services while guaranteeing the schedulability of the real-time tasks. We study two approaches to solve the security-aware optimization problem. Experimental results show that the combined security values are substantially higher than those achieved by alternatives for real-time tasks without violating real-time constraints.

Load balancing for clusters has been investigated extensively, mainly focusing on the effective usage of global CPU and memory resources. However, previous CPU- or memory-centric load balancing schemes suffer significant performance drop under I/O-intensive workloads due to the imbalance of I/O load. To solve this problem, we propose two simple yet effective I/O-aware load-balancing schemes for two types of clusters: (1) homogeneous clusters where nodes are identical and (2) heterogeneous clusters, which are comprised of a variety of nodes with different performance characteristics in computing power, memory capacity, and disk speed. In addition to assigning I/O-intensive sequential and parallel jobs to nodes with light I/O loads, the proposed schemes judiciously take into account both CPU and memory load sharing in the system. Therefore, our schemes are able to maintain high performance for a wide spectrum of workloads. We develop analytic models to study mean slowdowns, task arrival, and transfer processes in system levels. Using a set of real I/O-intensive parallel applications and synthetic parallel jobs with various I/O characteristics, we show that our proposed schemes consistently improve the performance over existing non-I/O-aware load-balancing schemes, including CPU- and Memory-aware schemes and a PBS-like batch scheduler for parallel and sequential jobs, for a diverse set of workload conditions. Importantly, this performance improvement becomes much more pronounced when the applications are I/O-intensive. For example, the proposed approaches deliver 23.6--88.0 % performance improvements for I/O-intensive applications such as LU decomposition, Sparse Cholesky, Titan, Parallel text searching, and Data Mining. When I/O load is low or well balanced, the proposed schemes are capable of maintaining the same level of performance as the existing non-I/O-aware schemes.

In the past decades, distributed systems have been widely applied to real-time applications, most of which have fault-tolerance requirements to assure high reliability. Due to the stringent space constraints of real-time systems, the issue of schedulability becomes a major concern in the design of fault-tolerant and real-time distributed systems. Most existing real-time and fault-tolerant scheduling algorithms, which are based on the primary-backup scheme for periodic real-time tasks, introduce unnecessary redundancies by aggressively using active-backup copies. To solve this problem, we propose two novel fault-tolerant techniques, which are seamlessly integrated with fixed-priority-based scheduling algorithms. These techniques leverage redundancies to enhance schedulability in fault-tolerant and real-time distributed systems. Our fault-tolerant techniques make use of the primary-backup scheme to tolerate permanent hardware failures. The first technique (referred to as Tercos) terminates the execution of active-backup copies, when corresponding primary copies are successfully completed. Tercos is designed to reduce scheduling lengths in fault-free scenarios to enhance schedulability by virtue of executing portions of active-backup copies in passive forms. The second technique (referred to as Debus) uses a deferred-active-backup scheme to further minimize schedule lengths to improve the schedulability performance. Debus schedules active-backup copies as late as possible, while terminating active-backup copies when their primary copies are completed. Experimental results show that, compared with existing algorithms in literature, Tercos can significantly improve schedulability by up to 17.0% (with an average of 9.7%). Furthermore, empirical results reveal that Debus can enhance schedulability over Tercos by up to 12% (with an average of 7.8%).

In the past decade parallel disk systems have been highly scalable and able to alleviate the problem of disk I/O bottleneck, thereby being widely used to support a wide range of data-intensive applications. Optimizing energy consumption in parallel disk systems has strong impacts on the cost of backup power-generation and cooling equipment, because a significant fraction of the operation cost of data centres is due to energy consumption and cooling. Although a variety of parallel disk systems were developed to achieve high performance and energy efficiency, most existing parallel disk systems lack an adaptive way to conserve energy in dynamically changing workload conditions. To solve this problem, we develop an adaptive energy-conserving algorithm, or DCAPS, for parallel disk systems using the dynamic voltage scaling technique that dynamically choose the most appropriate voltage supplies for parallel disks while guaranteeing specified performance (i.e., desired response times) for disk requests. We conduct extensive experiments to quantitatively evaluate the performance of the proposed energy-conserving strategy. Experimental results consistently show that DCAPS significantly reduces energy consumption of parallel disk systems in a dynamic environment over the same disk systems without using the DCAPS strategy.

Although data duplications may be able to improve the performance of data-intensive applications on data grids, a large number of data replicas inevitably increase energy dissipation in storage resources on the data grids. In order to implement a data grid with high energy efficiency, we address in this study the issue of energy-efficient scheduling for data grids supporting real-time and data-intensive applications. Taking into account both data locations and application properties, we design a novel Distributed Energy-Efficient Scheduler (or DEES for short) that aims to seamlessly integrate the process of scheduling tasks with data placement strategies to provide energy savings. DEES is distributed in the essence - it can successfully schedule tasks and save energy without knowledge of a complete grid state. DEES encompasses three main components: energy-aware ranking, performance-aware scheduling, and energy-aware dispatching. By reducing the amount of data replications and task transfers, DEES effectively saves energy. Simulation results based on a real-world trace demonstrate that with respect to energy consumption, DEES conserves over 35% more energy than previous approaches without degrading the performance.

Large-scale parallel disk systems are frequently used to meet the demands of information systems requiring high storage capacities. A critical problem with these large-scale parallel disk systems is the fact that disks consume a significant amount of energy. To design economically attractive and environmentally friendly parallel disk systems, we developed two energy-aware prefetching strategies for parallel disk systems with disk buffers. First, we introduce a new buffer disk architecture that can provide significant energy savings for parallel disk systems while achieving high performance. Second, we design a prefetching approach to utilize an extra disk to accommodate prefetched data sets that are frequently accessed. Third, we develop a second prefetching strategy that makes use of an existing disk in the parallel disk system as a buffer disk. Compared with the first prefetching scheme, the second approach lowers the capacity of the parallel disk system. However, the second approach is more cost-effective and energy-efficient than the first prefetching technique. Finally, we quantitatively compare both of our prefetching approaches against two conventional strategies including a dynamic power management technique and a non-energy-aware scheme. Using empirical results we show that our novel prefetching approaches are able to reduce energy dissipation in parallel disk systems by 44% and 50% when compared against a non-energy aware approach. Similarly, our strategies are capable of conserving 22% and 30% of the energy when compared to the dynamic power management technique.

As disk drives become increasingly sophisticated and processing power increases, one of the most critical issues of designing modern disk systems is data reliability. Although numerous energy saving techniques are available for disk systems, most of energy conservation techniques are not effective in reliability critical environments due to their limitation of ignoring the reliability issue. A wide range of factors affect the reliability of disk systems; the most important factors - disk utilization and ages — are the focus of this study. We build a model to quantify the relationship among the disk age, utilization, and failure probabilities. Observing that the reliability of a disk heavily relies on both disk utilization and age, we propose a novel concept of safe utilization zone, where energy of the disk can be conserved without degrading reliability. We investigate an approach to improving both reliability and energy efficiency of disk systems via utilization control, where disk drives are operated in safe utilization zones to minimize the probability of disk failure. In this study, we integrate an existing energy consumption technique that operates the disks at different power modes with our proposed reliability approach. Experimental results show that our approach can significantly improve reliable while achieving high energy efficiency for disk systems.

Security requirements and power management have become important criteria for data storage systems in today's world of information security. There exist many security approaches and power optimization techniques for storage systems but most of the existing approaches either concentrate on security or power management. Our approach integrates the power optimization with confidentiality services to maintain the secrecy of the data. Several traditional power optimization techniques involve stopping the disk completely when the loads on the storage disks are really low. Our approach makes use of the new evolving technique, Dynamic Speed Control for power management (DRPM), when the idle times between the requests are not very high. There are numerous security services like confidentiality, integrity, authentication and non-repudiation that can be provided to secure the data or information communication between parties. We concentrate on confidentiality which is one of the most popular requirements for security services.

High availability is a key requirement in the design and development of heterogeneous systems where processors operate at different speeds and are not continuously available for computation. Most existing scheduling algorithms designed for heterogeneous systems do not factor in availability requirements imposed by multiclass applications. To remedy this shortcoming, we investigate in this paper the scheduling problem for multiclass applications running in heterogeneous systems with availability constraints. In an effort to explore this issue, we model each node in a heterogeneous system using the node's computing capability and availability. Multiple classes of tasks are characterized by their execution times and availability requirements. To incorporate availability and heterogeneity into scheduling, we define new metrics to quantify system availability and heterogeneity for multiclass tasks. We then propose a scheduling algorithm to improve the availability of heterogeneous systems while maintaining good performance in the response time of tasks. Experimental results show that our algorithm achieves a good trade-off between availability and responsiveness.

Collaborative applications with energy and low-delay constraints are emerging in various networked embedded systems like wireless sensor networks and multimedia terminals. Conventional energy-aware task allocation schemes developed for collaborative applications only concentrated on energy savings when making allocation decisions. Consequently, the length of the schedules generated by such allocation schemes could be very long, which is unfavorable or, in some situations, even not tolerated. To remedy this problem, we developed a novel task allocation strategy called balanced energy-aware task allocation (BEATA) for collaborative applications running on heterogeneous networked embedded systems. The BEATA algorithm aims at blending an energy-delay efficiency scheme with task allocations, thereby making the best trade-offs between energy savings and schedule lengths. Aside from that, we introduced the concept of an energy-adaptive window, which is a critical parameter in the BEATA strategy. By fine-tuning the size of the energy-adaptive window, users can readily customize BEATA to meet their specific energy-delay trade-off needs imposed by applications. Further, we built a mathematical model to approximate the energy consumption caused by both computation and communication activities. Experimental results show that BEATA significantly improves the performance of embedded systems in terms of energy savings and schedule length over existing allocation schemes.

Security is increasingly becoming an important issue in the design of real-time parallel applications, which are widely used in the industry and academic organizations. However, existing resource allocation schemes for real-time parallel jobs on clusters generally do not factor in security requirements when making allocation and scheduling decisions. In this paper, we develop two resource allocation schemes, called task allocation for parallel applications with deadline and security constraints (TAPADS) and security-aware and heterogeneity-aware resource allocation for parallel jobs (SHARP), by taking into account applications' timing and security requirements in addition to precedence constraints. We consider two types of computing platforms: homogeneous clusters and heterogeneous clusters. To facilitate the presentation of the new schemes, we build mathematical models to describe a system framework, security overhead, and parallel applications with deadline and security constraints. The proposed schemes are applied to heuristically find resource allocations that maximize the quality of security and the probability of meeting deadlines for parallel applications running on clusters. Extensive experiments using real-world applications and traces, as well as synthetic benchmarks, demonstrate the effectiveness and practicality of the proposed schemes.

Modern real-time wireless networks require high security level to assure confidentiality of information stored in packages delivered through wireless links. However, most existing algorithms for scheduling independent packets in real-time wireless networks ignore various security requirements of the packets. Therefore, in this paper we remedy this problem by proposing a novel dynamic security-aware packet-scheduling algorithm, which is capable of achieving high quality of security for realtime packets while making the best effort to guarantee realtime requirements (e.g., deadlines) of those packets. We conduct extensive simulation experiments to evaluate the performance of our algorithm. Experimental results show that compared with two baseline algorithms, the proposed algorithm can substantially improve both quality of security and real-time packet guarantee ratio under a wide range of workload characteristics.

An increasing number of real-time parallel applications on clusters, such as aircraft control and medical electronics systems, require high quality of security to assure confidentiality, authenticity, and integrity of information. Conventional scheduling algorithms for clusters have been proposed to achieve high performance of parallel applications without security requirements; however, enhancing security of clusters for parallel applications requiring service flexibility remains an open problem. In this tutorial, we will discuss our current research that focuses on developing and evaluating new scheduling mechanisms and algorithms for applications with timing and security constraints on clusters. In particular, we will first describe an adaptive control framework for quality of security in cluster computing systems. The framework is centered on a model of security-sensitive real-time applications and security overhead model. The overhead model is used to measure security overheads incurred by an array of security services, including encryption, authentication, integrity check, etc. Next, we will describe a dynamic real-time scheduling algorithm, or TAPADS (Task Allocation for Parallel Applications with Deadline and Security constraints), which seamlessly integrates security requirements into real-time scheduling for clusters. To quantitatively evaluate the performance TAPADS, we conducted extensive experiments using real world applications and traces as well as synthetic benchmarks. We will present experimental results to demonstratively show that TAPADS significantly improves system performance in terms of quality of security and schedulability over three existing scheduling algorithms.

Real time applications such as military aircraft flight control systems and online banking are critical with respect to security and reliability. In this paper we presented a way to integrate both by considering confidentiality and integrity services for security and nonuniform checkpoint strategy for reliability. The slack exploitation interacts in subtle ways for security in regards to the placement of checkpoint. The checkpoints are placed in to the task at low frequency in the beginning because the slack available can accommodate a large amount of work at risk and the frequency is increased there after considering the slack available. The security is applied to the data in two ways. First method introduces the security for the entire data at once whereas in the second method the data is divided into n uneven sections and each section is separately secured . That is at the start of the task basic security services are considered depending on the slack available. The security is increased gradually for the rest of the task but if there exist a fault, then at that point the security is maintained at the steady rate because of the limited slack. Compared to the first method the second method can provide up to a 32.3 percent higher security. While compared to the traditional checkpoint strategy, the non-uniform check pointing makes more efficient use of slack while increasing the overall security levels by 34.4 percent for the second method.

In the past decade cluster computing platforms have been widely applied to support a variety of scientific and commercial applications, many of which are parallel in nature. However, scheduling parallel applications on large scale clusters is technically challenging due to significant communication latencies and high energy consumption. As such, shortening schedule length and conserving energy consumption are two major concerns in designing economical and environmentally friendly clusters. In this paper, we propose an energy-efficient scheduling algorithm (TDVAS) using the dynamic voltage scaling technique to provide significant energy savings for clusters. The TDVAS algorithm aims at judiciously leveraging processor idle times to lower processor voltages (i.e., the dynamic voltage scaling technique or DVS), thereby reducing energy consumption experienced by parallel applications running on clusters. Reducing processor voltages, however, can inevitably lead to increased execution times of parallel task. The salient feature of the TDVAS algorithm is to tackle this problem by exploiting tasks precedence constraints. Thus, TDVAS applies the DVS technique to parallel tasks followed by idle processor times to conserve energy consumption without increasing schedule lengths of parallel applications. Experimental results clearly show that the TDVAS algorithm is conducive to reducing energy dissipation in large-scale clusters without adversely affecting system performance.

High performance clusters have been widely used to provide amazing computing capability for both commercial and scientific applications. However, huge power consumption has prevented the further application of large-scale clusters. Designing energy-efficient scheduling algorithms for parallel applications running on clusters, especially on the high performance heterogeneous clusters, is highly desirable. In this regard, we propose a novel scheduling strategy called energy efficient task duplication schedule (EETDS for short), which can significantly conserve power by judiciously shrinking communication energy cost when allocating parallel tasks to heterogeneous computing nodes. We present the preliminary simulation results for Gaussian and FFT parallel task models to prove the efficiency of our algorithm.

Existing packets scheduling algorithms designed for energy-efficient wireless networks ignore important features of periodic packets, thereby being inadequate for periodic packets with energy constraints. To remedy this problem, we present in this paper an approach to scheduling periodic packets in wireless networks subject to both timing and energy constraints. We propose a necessary and sufficient feasibility check for a set of periodic packets to be transmitted over a wireless link. Next, we develop an algorithm to schedule periodic packets (or ESPP for short) over a wireless link. The ESPP algorithm aims at minimizing energy dissipation of periodic packets without missing deadlines of periodic packets. We show through simulation studies that ESPP can significantly reduce energy consumption of wireless networks by an average of 46.4% while guaranteeing timing constraints of periodic packets.

Huge energy consumption has become a critical bottleneck for further applying large-scale cluster systems to build new data centers. Among various components of a data center, storage subsystems are one of the biggest consumers of energy. In this paper, we propose a novel buffer-disk based framework for large-scale and energy-efficient parallel storage systems. To validate the efficiency of the proposed framework, a buffer-disk scheduling algorithm is designed and implemented. Our algorithm can provide more opportunities for underlying disk power management schemes to save energy by keeping a large number of idle data disks in sleeping mode as long as possible. The trace-driven simulation results based on a revised disksim simulator show that this new framework can significantly improves the energy efficiency of large-scale parallel storage systems.

In this paper, we propose a novel fault-tolerant technique, which is seamlessly integrated with fixed-priority-based scheduling algorithm to explore redundancies to enhance schedulability in fault-tolerant and real-time distributed systems. Our fault-tolerant technique makes use of the primary-backup scheme to tolerate permanent hardware failures. Most importantly, the proposed technique (referred to as Tercos) terminates the execution of active backup copies when corresponding primary copies are successfully completed, therefore Tercos can reduce scheduling lengths in fault-free scenario to enhance schedulability by virtue of executing portions of active backup copies in passive forms. Experimental results show that compared with existing algorithm in literature, Tercos can significantly improve schedulability by up to 17.0%(with an average of 9.7%).

While many scheduling algorithms for periodic tasks ignore security requirements posed by sensitive applications and are, consequently, unable to perform properly in embedded systems with security constraints, in this paper, we present an approach to scheduling periodic tasks in embedded systems subject to security and timing constraints. We design a necessary and sufficient feasibility check for a set of periodic tasks with security requirements. With the feasibility test in place, we propose a scheduling algorithm, or SASES (security-aware scheduling for embedded systems), which accounts for both security and timing requirements. SASES judiciously distributes slack times among a variety of security services for a set of periodic tasks, thereby optimizing security for embedded systems without sacrificing schedulability. To demonstrate the effectiveness of SASES, we apply the proposed SASES to real-world embedded systems such as an automated flight control system. We show, through extensive simulations, that SASES is able to maximize security for embedded systems while guaranteeing timeliness. In particular, SASES significantly improves security over three baseline algorithms by up to 107%.

High availability plays an important role in heterogeneous clusters, where processors operate at different speeds and are not continuously available for processing. Existing scheduling algorithms designed for heterogeneous clusters do not factor in availability. We address in this paper the stochastic scheduling problem for heterogeneous clusters with availability constraints. Each node in a heterogeneous cluster is modeled by its speed and availability, and different classes of tasks submitted to the cluster are characterized by their execution times and availability requirements. To incorporate availability and heterogeneity into stochastic scheduling, we introduce metrics to quantify availability and heterogeneity in the context of multiclass tasks. A stochastic scheduling algorithm SSAC (Stochastic Scheduling with Availability Constraints) is then proposed to improve availability of heterogeneous clusters while reducing average response time of tasks. Experimental results show that our algorithm achieves a good trade-off between availability and responsiveness

Optimizing energy consumption has become a major concern in designing economical clusters. Scheduling precedence-constrained parallel tasks on clusters is challenging because of high communication overhead. Although duplication-based strategies are applied to minimize communication overhead, most of them merely consider schedule lengths, completely ignoring energy consumption of clusters. In this regard, we propose two energy-aware duplication scheduling algorithms, called EADUS and TEBUS, to schedule precedence-constrained parallel tasks. Unlike existing duplication-based scheduling algorithms that replicate all possible predecessors of each task, the proposed algorithms judiciously replicate predecessors only if the duplication can help in conserving energy. Our energy-aware scheduling strategies are conducive to balancing the scheduling length and energy consumption of precedence-constrained parallel tasks. Extensive experimental results based on real-world applications demonstrate the effectiveness and practicality of the proposed scheduling strategies

Parallel disk systems, which have been widely used in building networked and data intensive applications, are highly scalable and can alleviate the problem of disk I/O bottleneck. Although a number of parallel disk systems have been developed, the systems lack a means to optimize quality of security for dynamically changing networked environments. We remedy this situation by proposing an adaptive quality of security control scheme for networked parallel disk systems (or ASPAD for short) that makes it possible for networked disk systems to adapt to changing security requirements and workload conditions. ASPAD is carried out in three phases: dynamic data partitioning, response time estimation, and adaptive security quality control. Hence, ASPAD is conducive to adaptively and expeditiously determining security schemes for disk requests in a way to improve security of networked parallel disk systems while making an effort to guarantee desired response times of the requests. To prove the efficiency of the proposed approach, we simulate a networked parallel disk system into which nine cryptographic schemes are integrated. Empirical results show that ASPAD significantly improves overall performance over an existing strategy with an average of 65%.

Parallel applications with energy and low-latency constraints are emerging in various networked embedded systems like digital signal processing, vehicle tracking, and infrastructure monitoring. However, conventional energy-driven task allocation schemes for a cluster of embedded nodes only concentrate on energy-saving when making allocation decisions. Consequently, the length of the schedules could be very long, which is unfavorable or in some situations even not tolerated. In this paper, we address the issue of allocating a group of parallel tasks on a heterogeneous embedded system with an objective of energy-saving and short-latency. A novel task allocation strategy, or BEATA (balanced energy-aware task allocation), is developed to find an optimal allocation that minimizes overall energy consumption while confining the length of schedule to an ideal range. Experimental results show that BEATA significantly improves the performance of embedded systems in terms of energy-saving and schedule length over an existing allocation scheme

Since security is of critical importance for modern storage systems, it is imperative to protect stored data from being tampered or disclosed. Although an increasing number of secure storage systems have been developed, there is no way to dynamically choose security services to meet disk requests' flexible security requirements. Furthermore, existing security techniques for disk systems are not suitable to guarantee desired response times of disk requests. We remedy this situation by proposing an adaptive strategy (referred to as AWARDS) that can judiciously select the most appropriate security service for each write request while endeavoring to guarantee the desired response times of all disk requests. Experimental results show that AWARDS significantly improves security and overall performance over an existing scheme by up to 325.0% and 358.9% (with averages of 199.3% and 213.4%)

This paper addresses the problem of improving quality of security for real-time parallel applications on heterogeneous clusters. We propose a new security- and heterogeneity-driven scheduling algorithm (SHARP for short), which strives to maximize the probability that parallel applications are executed in time without any risk of being attacked. Because of high security overhead in existing clusters, an important step in scheduling is to guarantee jobs' security requirements while minimizing overall execution times. The SHARP algorithm accounts for security constraints in addition to different processing capabilities of each node in a cluster. We introduce two novel performance metrics, degree of security deficiency and risk-free probability, to quantitatively measure quality of security provided by a heterogeneous cluster. Both security and performance of SHARP are compared with two well-known scheduling algorithms. Extensive experimental studies using real-world traces confirm that the proposed SHARP algorithm significantly improves security and performance of parallel applications on heterogeneous clusters

Security-critical real-time applications such as military aircraft flight control systems have mandatory security requirements in addition to stringent timing constraints. Conventional real-time scheduling algorithms, however, either disregard applications' security needs and thus expose the applications to security threats or run applications at inferior security levels without optimizing security performance. In recognition that many applications running on clusters demand both real-time performance and security, we investigate the problem of scheduling a set of independent real-time tasks with various security requirements. We build a security overhead model that can be used to reasonably measure security overheads incurred by the security-critical tasks. Next, we propose a security-aware real-time heuristic strategy for clusters (SAREC), which integrates security requirements into the scheduling for real-time applications on clusters. Further, to evaluate the performance of SAREC, we incorporate the earliest deadline first (EDF) scheduling policy into SAREC to implement a novel security-aware real-time scheduling algorithm (SAEDF). Experimental results from both real-world traces and a real application show that SAEDF significantly improves security over three existing scheduling algorithms (EDF, least laxity first, and first come first serve) by up to 266.7 percent while achieving high schedulability.

Since security is of critical importance for modern storage systems, it is imperative to protect stored data from being tampered with or disclosed. Although an increasing number of secure storage systems have been developed, there is no way to dynamically choose security services to meet disk requests' flexible security requirements. Furthermore, existing security techniques for disk systems are not suitable to guarantee desired response times of disk requests. We remedy this situation by proposing an adaptive strategy (referred to as AWARDS) that can judiciously select the most appropriate security service for each write request, while endeavoring to guarantee the desired response times of all disk requests. To prove the efficiency of the proposed approach, we build an analytical model to measure the probability that a disk request is completed before its desired response time. The model also can be used to derive the expected value of disk requests' security levels. Empirical results based on synthetic workloads as well as real I/O-intensive applications show that AWARDS significantly improves overall performance over an existing scheme by up to 358.9% (with an average of 213.4%).

Parallel applications with deadline and security constraints are emerging in various areas like education, information technology, and business. However, conventional job schedulers for clusters generally do not take security requirements of realtime parallel applications into account when making allocation decisions. In this paper, we address the issue of allocating tasks of parallel applications on clusters subject to timing and security constraints in addition to precedence relationships. A task allocation scheme, or TAPADS (task allocation for parallel applications with deadline and security constraints), is developed to find an optimal allocation that maximizes quality of security and the probability of meeting deadlines for parallel applications. In addition, we proposed mathematical models to describe a system framework, parallel applications with deadline and security constraints, and security overheads. Experimental results show that TAPADS significantly improves the performance of clusters in terms of quality of security and schedulability over three existing allocation schemes

Security requirements of security-critical real-time applications must be met in addition to satisfying timing constraints. However, conventional real-time scheduling algorithms ignore the applications' security requirements. In recognition that an increasing number of applications running on clusters demand both real-time performance and security, we investigate the problem of scheduling a set of independent real-time tasks with various security requirements. We propose a security overhead model that is capable of measuring security overheads incurred by security-critical tasks. Further, we propose a security-aware scheduling strategy, or SAREC, which integrates security requirements into scheduling for real-time applications by employing our security overhead model. To evaluate the effectiveness of SAREC, we implement a security-aware real-time scheduling algorithm (SAREC-EDF), which incorporates the earliest deadline first (EDF) scheduling algorithm into SAREC Extensive simulation experiments show that SAREC-EDF significantly improves overall system performance over three baseline scheduling algorithms (variations of EDF) by up to 72.55%.

Summary form only given. Clusters have emerged as a primary and cost-effective infrastructure for parallel applications, including communication-intensive applications that transfer a large amount of data among nodes of a cluster via the interconnection network. Conventional load balancers have been proven effective in increasing the utilization of CPU, memory, and disk I/O resources in a cluster. However, most of the existing load balancing schemes ignore network resources, leaving open the opportunity for significant performance bottleneck to form for communication-intensive parallel applications due to unevenly distributed communication load. To remedy this problem, we propose a communication-aware load balancing technique that is capable of improving the performance of communication-intensive applications by increasing the effective utilization of network resources in clusters. To facilitate the proposed load-balancing scheme, we introduce a behavior model for parallel applications with large requirements of CPU, memory, network, and disk 170 resources. The proposed load-balancing scheme can make full use of this model to quickly and accurately determine the load induced by a variety of parallel applications. Simulation results on executing a diverse set of both synthetic bulk synchronous and real parallel applications on a cluster show that the proposed scheme can significantly improve the performance both in slowdown and turn-around time over three existing schemes by up to 206% (with an average of 74%) and 235% (with an average of 82%), respectively.

Due to the ever-widening performance gap between processors and disks, I/O operations tend to become the major performance bottleneck of data-intensive applications on modern clusters. If all the existing disks on the nodes of a cluster are connected together to establish high performance parallel storage systems, the cluster's overall performance can be boosted at no additional cost. CEFT-PVFS (a RAID 10 style parallel file system that extends the original PVFS), as one such system, divides the cluster nodes into two groups, stripes the data across one group in a round-robin fashion, and then duplicates the same data to the other group to provide storage service of high performance and high reliability. Previous research has shown that the system reliability is improved by a factor of more than 40 with mirroring while maintaining a comparable write performance. This paper presents another benefit of CEFT-PVFS in which the aggregate peak read performance can be improved by as much as 100% over that of the original PVFS by exploiting the increased parallelism. Additionally, when the data servers, which typically are also computational nodes in a cluster environment, are loaded in an unbalanced way by applications running in the cluster, the read performance of PVFS will be degraded significantly. On the contrary, in the CEFT-PVFS, a heavily loaded data server can be skipped and all the desired data is read from its mirroring node. Thus the performance will not be affected unless both the server node and its mirroring node are heavily loaded.

While previous CPU- or memory-centric load balancing schemes are capable of achieving the effective usage of global CPU and memory resources in a cluster system, the cluster exhibits significant performance drop under I/O-intensive workload conditions due to the imbalance of I/O load. To tackle this problem, we have developed two simple yet effective I/O-aware load-balancing schemes, which make it possible to balance I/O load by assigning I/O intensive sequential and parallel jobs to nodes with light I/O loads. Moreover, the proposed schemes judiciously take into account both CPU and memory load sharing in the cluster, thereby maintaining a high performance for a wide spectrum of workload. Using a set of real I/O-intensive parallel applications in addition to synthetic parallel jobs, we show that the proposed schemes consistently outperform the existing non-I/O aware load-balancing schemes for a diverse set of workload conditions. Importantly, the performance improvement becomes much more pronounced when the applications are I/O-intensive.

In this paper we analyze the I/O access patterns of a widely-used biological sequence search tool and implement two variations that employ parallel-I/O for data access based on PVFS (Parallel Virtual File System) and CEFT-PVFS (cost-effective fault-tolerant PVFS). Experiments show that the two variations outperform the original tool when equal or even fewer storage devices are used in the former. It is also found that although the performance of the two variations improves consistently when initially increasing the number of servers, this performance gain from parallel I/O becomes insignificant with further increase in server number. We examine the effectiveness of two read performance optimization techniques in CEFT-PVFS by using this tool as a benchmark. Performance results indicate: (1) doubling the degree of parallelism boosts the read performance to approach that of PVFS; and (2) skipping hot-spots can substantially improve the I/O performance when the load on data servers is highly imbalanced. The I/O resource contention due to the sharing of server nodes by multiple applications in a cluster has been shown to degrade the performance of the original tool and the variation based on PVFS by up to 10 and 21 folds, respectively; whereas, the variation based on CEFT-PVFS only suffered a two-fold performance degradation.

Load balancing in a cluster system has been investigated extensively, mainly focusing on the effective usage of global CPU and memory resources. However, if a significant portion of applications running in the system is I/O-intensive, traditional load balancing policies that focus on CPU and memory usage may cause the system performance to decrease substantially. To solve this problem, a new I/O-aware load-balancing scheme with preemptive job migration is presented to sustain the high performance of a cluster with a diverse set of workload conditions. The proposed scheme dynamically detects I/O load imbalance on nodes of a cluster, and determines whether to preempt some running jobs on overloaded nodes and migrate them to other less- or under-loaded nodes. Besides balancing I/O load, the scheme takes into account both CPU and memory load sharing in clusters, thereby maintaining the same level of performance as existing schemes when I/O load is low or well balanced. Results from a trace-driven simulation show that, compared to the existing approaches that only consider I/O with nonpreemptive job migrations, the proposed schemes achieve the improvement in mean slowdown by up to a factor of 10.

In this paper, we investigate an efficient off-line scheduling algorithm in which real-time tasks with precedence constraints are executed in a heterogeneous environment. It provides more features and capabilities than existing algorithms that schedule only independent tasks in real-time homogeneous systems. In addition, the proposed algorithm takes the heterogeneities of computation, communication and reliability into account, thereby improving the reliability. To provide fault-tolerant capability, the algorithm employs a primary-backup copy scheme that enables the system to tolerate permanent failures in any single processor. In this scheme, a backup copy is allowed to overlap with other backup copies on the same processor, as long as their corresponding primary copies are allocated to different processors. Tasks are judiciously allocated to processors so as to reduce the schedule length as well as the reliability cost, defined to be the product of processor failure rate and task execution time. In addition, the time for detecting and handling a permanent fault is incorporated into the scheduling scheme, thus making the algorithm more practical. To quantify the combined performance of fault-tolerance and schedulability, the performability measure is introduced Compared with the existing scheduling algorithms in the literature, our scheduling algorithm achieves an average of 16.4% improvement in reliability and an average of 49.3% improvement in performability.

In this paper, a heuristic dynamic scheduling scheme for parallel real-time jobs in a heterogeneous system is presented. The parallel real-time jobs studied in this paper are modelled by directed acyclic graphs (DAG). We assume a scheduling environment where parallel real-time jobs arrive at a heterogeneous system following a Poisson process. The scheduling algorithms developed in this paper take the reliability measure into account, in order to enhance the reliability of the heterogeneous system without any additional hardware cost. In addition, scheduling time and dispatch time are both incorporated into our scheduling scheme so as to make the scheduling result more realistic and precise. Admission control is in place so that a parallel real-time job whose deadline cannot be guaranteed is rejected by the system. The performance of the proposed scheme is evaluated via extensive simulations. The simulation results show that the heuristic algorithm performs significantly better than two other algorithms that do not consider reliability cost. Furthermore, results suggest that shortening the scheduling time results in a higher guarantee ratio. Hence, if parallel scheduling algorithm is devised and employed to shorten the scheduling time, the performance of the heterogeneous system will be further enhanced.