Implementing an efficient k-Nearest Neighbors (kNN) algorithm on FPGA is becoming challenging due to the fact that both the size and dimensionality of datasets that kNN is working on have been rapidly growing, which makes external memory-access a performance bottleneck. To reduce the impact of the bottleneck, in this paper we implement two kNN kernels through high-level synthesis (HLS) on FPGA by employing two data access reduction methods: low-precision data representation (LPDR) and principal component analysis based filtering (PCAF). One kernel is called MBFS-kNN (Memory-efficient Brute-Force Searching kNN) and the other is called MPCAF-kNN (Memory-efficient PCAF kNN). The two kernels are adaptive to all key parameters. By comparing them with two state-of-the-art kNN implementations on a high-end CPU server, an existing BFS-kNN kernel on FPGA, and an existing BFS-kNN kernel on GPU, our experimental results show that the two kernels substantially improve the performance by greatly reducing external memory-accesses.

Visual molecular dynamics (VMD) has been widely used by numerous molecular dynamics (MD) applications to animate and analyze the trajectory of an MD simulation. One challenge faced by domain scientists, however, is how to filter out inactive data (i.e., data irrelevant to the subject) from the enormous output of an MD simulation. To solve it, we propose ADA (application-conscious data acquirer), a light-weight file system middleware that can perform an application-conscious data pre-processing. It provides host CPUs with only the data needed instead of an entire raw dataset. Next, we implement an ADA prototype, which is then integrated into three computing platforms: an SSD server, a nine-node OrangeFS storage cluster, and a fat-node server with 1 TB memory. Further, we evaluate ADA by running a computational biology application on the three platforms. Our experimental results show that compared to a traditional file system an ADA-assisted file system improves data processing turnaround time by up to 13.4x and reduces memory usage for data rendering by up to 2.5x. Besides, ADA allows the 1TB memory server to render more than 2x the VMD graphs while cutting energy consumption by 3x.

Existing near-data processing (NDP)-powered architectures have demonstrated their strength for some data-intensive applications. Data center servers, however, have to serve not only data-intensive but also compute-intensive applications. An in-depth understanding of the impact of NDP on various data center applications is still needed. For example, can a compute-intensive application also benefit from NDP? In addition, current NDP techniques focus on maximizing the data processing rate by always utilizing all computing resources at all times. Is this “always running in full gear” strategy consistently beneficial for an application? To answer these questions, we first propose two reconfigurable NDP-powered servers called RANS ( R econfigurable A RM-based N DP S erver) and RFNS ( R econfigurable F PGA-based N DP S erver). Next, we implement a single-engine prototype for each of them based on a conventional data center and then evaluate their effectiveness. Experimental results measured from the two prototypes are then extrapolated to estimate the properties of the two full-size reconfigurable NDP servers. Finally, several new findings are presented. For example, we find that while RANS can only benefit data-intensive applications, RFNS can offer benefits for both data-intensive and compute-intensive applications. Moreover, we find that for certain applications the reconfigurability of RANS/RFNS can deliver noticeable energy efficiency without any performance degradation.

We present BORA (Bag Optimizer for Robotic Analysis), a file system middleware that optimizes the acquisition of bags, which are specially formatted files used to store timestamped ROS (robot operating system) messages. BORA sits between ROS and an existing file system to conduct semantic-aware data pre-processing. In particular, it categorizes ROS bag data into multiple groups with each having a distinct label. BORA predigests data index constructions and reduces file open time via a hash-based label management scheme. It is also capable of providing ROS analytic applications with only data needed without a sequence of data searching and locating operations. We implement a BORA prototype, which is then integrated into three computing platforms: a single-node server, a four-node PVFS storage cluster, and a Tianhe-1A Supercomputer storage subsystem. Next, we evaluate the BORA prototype on the three platforms using four real-world ROS applications. Our experimental results show that compared to a traditional bag management scheme BORA improves data acquisition performance by up to 11x. In addition, it offers up to 10x data acquisition performance improvement and 3,100x bags open improvement under a swarm robotics data analysis scenario where data is retrieved across multiple bags simultaneously.

Implementing an efficient k-Nearest Neighbors(kNN) algorithm on FPGA is becoming challenging due to the fact that both the size and dimensionality of datasets that kNN is working on have been rapidly growing, which may incur a performance bottleneck on the memory-access. To reduce the impact of the memory-access constraint, in this paper we implement two kNN kernels through high-level synthesis (HLS) on FPGA by employing two data access reduction methods: low-precision data representation and principal component analysis based filtering (PCAF). One kernel is called MBFSkNN (Memory-efficient Brute-Force Searching kNN) and the other is called MPCAF-kNN (Memory-efficient PCAF kNN). Both kernels have been highly optimized to fully exploit the characteristics of FPGA. Besides, they are adaptive to the number of dimensions (D), number of data points in a database (N), number of nearest neighbors (k), number of bits per feature (B), and number of principal components (d). We evaluate the two kernels by comparing them with two state-of-the-art kNN implementations on a high-end CPU server, an existing BFS-kNN kernel on FPGA, and an existing BFS-kNN kernel on GPU. Our results show that the external memory accesses of these two kernels are greatly reduced and our design outperforms the existing ones.

To reduce the impact of the memory-access constraint in k-Nearest Neighbors (kNN) problems, in this paper we implement one kNN kernel through high-level synthesis (HLS) on FPGA by employing two data access reduction methods: low-precision data representation and principal component analysis based filtering (PCAF). The kernel is called MPCAF-kNN (Memory-efficient PCAF kNN), which has been highly optimized to fully exploit the characteristics of FPGA. It is adaptive to all key parameters. We evaluate MPCAF-kNN by comparing it with a state-of-the-art kNN implementation on a high-end CPU server. Our results show that MPCAF-kNN achieves up to a performance equivalent to that of a 56-thread of CPU server while greatly reducing external memory-accesses.

Persistent memory (PM) exhibits a huge potential to provide applications with a hybrid memory system where both DRAM and PM are directly connected to a CPU. In such a system, an efficient indexing data structure such as a persistent tree becomes an indispensable component. Designing a capable persistent tree, however, is challenging as it has to ensure consistency, persistence, and scalability without substantially degrading performance. Besides, it needs to prevent persistent memory leaks. While hash table has been widely used for main memory indexing due to its superior performance in random query, ART (Adaptive Radix Tree) is inherently better than B/B+-tree in most basic operations on both DRAM and PM. To exploit their complementary merits, in this paper we propose a novel concurrent and persistent tree called HART (Hashassisted ART), which employs a hash table to manage ARTs. HART employs a selective consistency/persistence mechanism and an enhanced persistent memory allocator, which can not only optimize its performance but also prevent persistent memory leaks. Experimental results show that in most cases HART significantly outperforms WOART and FPTree, two state-of-theart persistent trees. Also, it scales well in concurrent scenarios.

Existing in-storage processing (ISP) techniques mainly focus on maximizing data processing rate by always utilizing total storage data processing resources for all applications. We find that this "always running in full gear" strategy wastes energy for some applications with a low data processing complexity. In this paper we propose RISP (Reconfigurable ISP), an energy-aware reconfigurable ISP framework that employs FPGA as data processing cells and NVM controllers. It can reconfigure storage data processing resources to achieve a high energy-efficiency without any performance degradation for big data analysis applications. RISP is modeled and then validated on an FPGA board. Experimental results show that compared with traditional host-CPU based computing RISP (with 16 channels or more) improves performance by 1.6-25.4× while saving energy by a factor of 2.2-161. Further, its reconfigurability can provide up to 77.2% additional energy saving by judiciously enabling data processing resources that are sufficient for an application.

Existing persistent memory (PM) based file systems rely on a DRAM and PM hybrid store. Although a hybrid store does boost system performance while avoiding some current PM limitations like limited endurance, we envision that with more advances PM technologies could provide applications with a single-level persistent store in the not-so-distant future. As a first step to explore this direction, in this paper we design, implement, and evaluate a new persistent memory file system called SPFS (Single-level Persistent File System), which completely bypasses conventional DRAM-based volatile main memory. Unlike all existing PM-based file systems, SPFS never leverages DRAM to manage its metadata. Thus, redundant copies of metadata in volatile main memory (e.g., a copy of an inode in DRAM) and data movements between the two memories (e.g., copying an inode from PM to DRAM) can be totally eliminated. The goal of this paper is to explore how to manage files and their metadata with guaranteed data consistency on PM without the support of DRAM, which makes a first step towards the ultimate success of a single-level persistent store. Our experimental results demonstrate that SPFS outperforms traditional DRAM-based in-memory file systems ramfs and tmpfs in most cases. Besides, its performance is only moderately worse than that of NOVA, a state-of-the-art PM-based file system.

Simply applying an existing redundant array of independent disks (RAID) technique to enhance data reliability within a single solid-state drive for safety-critical mobile applications significantly degrades performance. In this article, we first propose a new RAID5 architecture called channel-RAID5 with mirroring (CR5M) to alleviate the performance degradation problem. Next, an associated data reconstruction strategy called mirroring-assisted channel-level reconstruction (MCR) is developed to further shrink the window of vulnerability. Experimental results demonstrate that compared with channel-RAID5 (CR5), CR5M improves performance up to 40.2%. Compared with disk-oriented reconstruction, a traditional data reconstruction scheme, MCR on average improves data recovery speed by 7.5% while delivering a similar performance during reconstruction.

Since little has been reported in the literature concerning enterprise storage system file-level request scheduling, we do not have enough knowledge about how various scheduling factors affect performance. Moreover, we are in lack of a good understanding on how to enhance request scheduling to adapt to the changing characteristics of workloads and hardware resources. To answer these questions, we first build a request scheduler prototype based on WAFL®, a mainstream file system running on numerous enterprise storage systems worldwide. Next, we use the prototype to quantitatively measure the impact of various scheduling configurations on performance on a NetApp®'s enterprise-class storage system. Several observations have been made. For example, we discover that in order to improve performance, the priority of write requests and non-preempted restarted requests should be boosted in some workloads. Inspired by these observations, we further propose two scheduling enhancement heuristics called SORD (size-oriented request dispatching) and QATS (queue-depth aware time slicing). Finally, we evaluate them by conducting a wide range of experiments using workloads generated by SPC-1 and SFS2014 on both HDD-based and all-flash platforms. Experimental results show that the combination of the two can noticeably reduce average request latency under some workloads.

NAND flash memory–based solid state disks (SSDs) have been widely used in enterprise servers. However, flash memory has limited write endurance, as a block becomes unreliable after a finite number of program/erase cycles. Existing wear-leveling techniques are essentially intradisk data distribution schemes, as they can only even wear out across the flash medium within a single SSD. When multiple SSDs are organized in an array manner in server applications, an interdisk wear-leveling technique, which can ensure a uniform wear-out distribution across SSDs, is much needed. In this article, we propose a novel SSD-array level wear-leveling strategy called SWANS ( S moothing W ear A cross N S SDs) for an SSD array structured in a RAID-0 format, which is frequently used in server applications. SWANS dynamically monitors and balances write distributions across SSDs in an intelligent way. Further, to evaluate its effectiveness, we build an SSD array simulator on top of a validated single SSD simulator. Next, SWANS is implemented in its array controller. Comprehensive experiments with real-world traces show that SWANS decreases the standard deviation of writes across SSDs on average by 16.7x. The gap in the total bytes written between the most written SSD and the least written SSD in an 8-SSD array shrinks at least 1.3x.

Flash memory based solid state drives (SSD) are increasingly common in portable and mobile computing devices such as laptops, mobile phones, and tablets. Due to space, weight, and power constraints, portable devices are often restricted to a single storage device, which makes them susceptible to data loss from internal errors. On the other hand, mission-critical mobile applications like wireless healthcare always demand a high level of data reliability. This is mainly because data sampled from mobile and dynamic environments are most likely irreproducible. An effective approach to improving storage and data reliability is the RAID (redundant arrays of inexpensive disks) organization. However, the multiple disks required to implement RAID make it incompatible with the aforementioned restrictions of many portable devices. In this paper, we propose a SIRF (single internally redundant flash) architecture that leverages the internal hierarchical structure and parallelism of SSDs to provide redundancy similar to RAID in a single drive configuration. The initial effort focuses on implementing SIRF-1 (mirroring), which is the corollary to its RAID-1 counterpart. In SIRF-1, data is mirrored across SSD channels to optimally exploit parallelism for both read and write operations. Simulation results show that for read-dominant workloads SIRF-1 significantly outperforms a non-mirrored SSD by up to 39.5% in terms of mean response time. For write-intensive workloads, SIRF-1 pays a performance penalty no more than 5.5%.

After investigating the data processing characteristics of several scientific applications in various disciplines from bioinformatics to geology, we discover that they share one common feature: raw data is written once onto a storage system and then it is read into memory once for analyzing, after which it will seldom be used in the future. Typically, these scientific applications are running on a cluster where the storage system of each node is composed of an array of hard disk drives (HDDs). Although HDDs are economical, they become increasingly incompetent to meet the high I/O performance requirements imposed by these applications. Flash memory based solid-state-drives (SSDs), on the other hand, can provide a high performance and energy-efficiency. Still, they are relatively expensive than HDDs. In this paper, we propose a cost-effective yet high-performance storage architecture called SOHO (SSD-Workshop-HDD-Warehouse) for these write-once-read-once scientific applications like seismic wave analysis. Its basic idea is to process raw data in the workshop (i.e., SSD), and then, the processed data is moved to the warehouse (i.e., HDD) later. Experiments using both real-world scientific applications and synthetic traces demonstrate that on average SOHO outperforms a pure HDD storage system in mean response time by 78.25%. Compared to a pure SSD system, it only degrades mean response time by less than 3.11%.

Retention error has been recognized as the most dominant error in MLC (multi-level cell) flash. In this paper, we propose a new approach called PISO (Programming Initial Step Only) to reduce its number. Unlike a normal programming operation, a PISO operation only carries out the first programming-and-verifying step on a programmed cell. As a result, a number of electrons are injected into the cell to compensate its charge loss over time without disturbing its existing data. Further, we build a model to understand the relationship between the number of PISOs and the number of reduced errors. Experimental results from 1y-nm MLC chips show that PISO can efficiently reduce the number of retention errors with a minimal overhead. On average, applying 10 PISO operations each month on a one-year-old MLC chip that has experienced 4K P/E cycles can reduce its retention errors by 21.5% after 3 months.

Existing embedded flash storage systems are built based on a single MTD (Memory Technology Device) architecture no matter how many raw flash devices exist under a flash controller. The single-MTD architecture impedes exploiting device-level parallelism to further improve the performance of a storage system. In this paper, we design and implement a new embedded flash storage framework called MA (MTD-array), which abstracts each underlying raw flash device as an independent MTD device to boost performance. To verify its effectiveness, we implement a new flash file system called MA-UBIFS by incorporating UBIFS, one of the best contemporary flash file systems, into MA in Ubuntu 13.04 with 3.8.0 kernel. Simulation results from real-world applications show that MA-UBIFS outperforms UBIFS in mean response time by up to 71.6%. Further, we build an FPGA evaluation platform. Results from the hardware platform show that on average MA-UBIFS improves write and read throughput in a 2-MTD scenario by 55.2% and 84%, respectively.

A software module named flash translation layer (FTL) running in the controller of a flash SSD exposes the linear flash memory to the system as a block storage device. The effectiveness of an FTL significantly impacts the performance and durability of a flash SSD. In this research, we propose a new FTL called PCFTL (Plane-Centric FTL), which fully exploits plane-level parallelism supported by modern flash SSDs. Its basic idea is to allocate updates onto the same plane where their associated original data resides on so that the write distribution among planes is balanced. Furthermore, it utilizes fast intra-plane copy-back operations to transfer valid pages of a victim block when a garbage collection occurs. We largely extend a validated simulation environment called SSDsim to implement PCFTL. Comprehensive experiments using realistic enterprise-scale workloads are performed to evaluate its performance with respect to mean response time and durability in terms of standard deviation of writes per plane. Experimental results demonstrate that compared with the well-known DFTL, PCFTL improves performance and durability by up to 47 and 80 percent, respectively. Compared with its earlier version (called DLOOP), PCFTL enhances durability by up to 74 percent while delivering a similar I/O performance.

MLC (multi-level cell) NAND flash memory based solid state drives (SSDs) have been increasingly used in supercomputing centers because of their merits in cost, performance, and energy-efficiency. However, as each cell starts to store two or more bits, a threshold voltage range employed to represent a state has to be continuously shrunk, and a narrowed threshold voltage range causes more bit errors. An ad-hoc solution to this problem is to apply an enhanced ECC (error correction code) scheme. Still, a comprehensive understanding of the impact of threshold voltage on MLC flash performance and reliability is an open question. In this paper, we first empirically measure the correlations between threshold voltage and program/erase (P/E) performance as well as reliability. After analyzing experimental results, we make several interesting observations: 1) a memory cell programmed to a lower threshold voltage has a faster programming speed (up to 31%) as well as a fewer number of bit errors; 2) the programming time of an MSB page is about 2 to 3 times shorter than that of an LSB page; 3) erase performance is highly correlated to threshold voltage. These new findings provide system implications for the development of a better SSD. Further, to demonstrate how these findings can be leveraged to enhance MLC flash, we propose an approach called threshold voltage reduction (TVR), which increases programming speed and longevity by 50% and 7.1%, respectively. Finally, we conduct a study on TVR-powered SSDs. Simulation results show that overall mean response time can be reduced by up to 35%.

Manufacturers are continuously pushing NAND flash memory into smaller geometries and enforce each cell to store multiple bits in order to largely reduce its cost. Unfortunately, these scaling down techniques inherently degrade the endurance and reliability of flash memory. As a result, permanent errors such as block or die failures could occur with a higher possibility. While most transient errors like programming errors can be fixed by an ECC (error correction code) scheme, rectifying permanent errors requires a data redundancy mechanism like RAID (redundant array of independent disks) in a single SSD where multiple channels work in parallel. To enhance the reliability of a solid-state drive (SSD) while maintaining its performance, we first implement several common RAID structures in the channel level of a single SSD to understand their impact on an SSD's performance. Next, we propose a new data redundancy architecture called CR5M (Channel-RAID5 with Mirroring), which can be applied to one SSD for mission-critical applications. CR5M utilizes hidden mirror chips to accelerate the performance of small writes. Finally, we conduct extensive simulations using real-world traces and synthetic benchmarks on a validated simulator to evaluate CR5M. Experimental results demonstrate that compared with CR5 (Channel-RAID5) CR5M decreases mean response time by up to 25.8%. Besides, it reduces the average writes per channel by up to 23.6%.

A flash translation layer (FTL) is a software layer running in the flash controller of a NAND flash memory solid-state disk (hereafter, flash SSD). It translates logical addresses received from a file system to physical addresses in flash SSD so that the linear flash memory appears to the system like a block storage device. Since the effectiveness of an FTL significantly impacts the performance and durability of a flash SSD, FTL design has attracted significant attention from both industry and academy in recent years. In this research, we propose a new FTL called DLOOP (Data Log On One Plane), which fully exploits plane-level parallelism supported by modern flash SSDs. The basic idea of DLOOP is to allocate logs (updates) onto the same plane where their associated original data resides so that valid page copying operations triggered by garbage collection can be carried out by intraplane copy-back operations without occupying the external I/O bus. Further, we largely extend a validated simulation environment DiskSim3.0/FlashSim to implement DLOOP. Finally, we conduct comprehensive experiments to evaluate DLOOP using realistic enterprise-scale workloads. Experimental results show that DLOOP consistently outperforms a classical hybrid FTL named FAST and a morden page-mapping FTL called DFTL.

Current disk arrays consist purely of hard disk drives, which normally provide huge storage capacities with low cost and high throughput for data-intensive applications. Nevertheless, they have some inherent disadvantages such as long access latencies and energy inefficiency due to their build-in mechanical mechanisms. Flash-memory-based solid state disks, on the other hand, although currently more expensive and inadequate in write cycles, offer much faster random read accesses and are much more robust and energy efficient. To combine the complementary merits of hard disks and flash disks, in this paper, we propose a hybrid disk array architecture named hybrid disk storage (HIT) for data-intensive applications. Next, a dynamic data redistribution strategy called performance, energy, and reliability balanced (PEARL), which can periodically redistribute data between flash disks and hard disks to adapt to the changing data access patterns, is developed on top of the HIT architecture. Comprehensive simulations using real-life traces demonstrate that compared with existing data placement techniques, PEARL exhibits its strength in both performance and energy consumption without impairing flash disk reliability.

Mobile disk arrays, disk arrays located in mobile data centers, are crucial for mobile applications such as disaster recovery. Due to their unusual application domains, mobile disk arrays face several new challenges including harsh operating environments, very limited power supply, and extremely small number of spare disks. Consequently, data reconstruction schemes for mobile disk arrays must be performance-driven, reliability-aware, and energy-efficient. In this paper, we develop a flash assisted data reconstruction strategy called CORE (collaboration-oriented reconstruction) on top of a hybrid disk array architecture, where hard disks and flash disks collaborate to shorten data reconstruction time, alleviate performance degradation during disk recovery. Experimental results demonstrate that CORE noticeably improves the performance and energy-efficiency over existing schemes.

The problem of statically assigning nonpartitioned files in a parallel I/O system has been extensively investigated. A basic workload characteristic assumption of most existing solutions to the problem is that there exists a strong inverse correlation between file access frequency and file size. In other words, the most popular files are typically small in size, while the large files are relatively unpopular. Recent studies on the characteristics of Web proxy traces suggested, however, the correlation, if any, is so weak that it can be ignored. Hence, the following two questions arise naturally. First, can existing algorithms still perform well when the workload assumption does not hold? Second, if not, can one develop a new file assignment strategy that is immune to the workload assumption? To answer these questions, we first evaluate the performance of three well-known file assignment algorithms with and without the workload assumption, respectively. Next, we develop a novel static nonpartitioned file assignment strategy for parallel I/O systems, called static round-robin (SOR), which is immune to the workload assumption. Comprehensive experimental results show that SOR consistently improves the performance in terms of mean response time over the existing schemes.

Mainstream energy conservation schemes for disk arrays inherently affect the reliability of disks. A thorough understanding of the relationship between energy saving techniques and disk reliability is still an open problem, which prevents effective design of new energy saving techniques and application of existing approaches in reliability-critical environments. As one step towards solving this problem, this paper presents an empirical reliability model, called Predictor of Reliability for Energy Saving Schemes (PRESS). Fed by three energy-saving-related reliability-affecting factors, operating temperature, utilization, and disk speed transition frequency, PRESS estimates the reliability of entire disk array. Further, a new energy saving strategy with reliability awareness called Reliability and Energy Aware Distribution (READ) is developed in the light of the insights provided by PRESS. Experimental results demonstrate that compared with existing energy saving schemes, MAID and PDC, READ consistently performs better in performance and reliability while achieving a comparable level of energy consumption.

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.

Many real-world applications need to frequently access data stored on large-scale parallel disk storage systems. On one hand, prompt responses to access requests are essential for these applications. On the other hand, however, with an explosive increase of data volume and the emerging of faster disks with higher power requirements, energy consumption of disk-based storage systems has become a salient issue. To achieve energy-conservation and prompt responses simultaneously, in this paper we propose a novel energy-aware strategy, called striping-based energy-aware (SEA), which can be integrated into data placement in RAID-structured storage systems to noticeably save energy while providing quick responses. Next, to illustrate the effectiveness of SEA, we implement two SEA-powered striping-based data placement algorithms, SEA0 and SEA5, by incorporating the SEA strategy into RAID-0 and RAID-5, respectively. Extensive experimental results demonstrate that compared with traditional non-stripping data placement algorithms, our algorithms significantly improve performance and save energy. Further, compared with an existing stripping-based data placement scheme, the two SEA-powered strategies noticeably reduce energy consumption with only a little performance degradation.

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.

High performance, highly reliable, and energy-efficient storage systems are essential for mobile data-intensive applications such as remote surgery and mobile data center. Compared with conventional stationary storage systems, mobile disk-array-based storage systems are more prone to disk failures due to their severe application environments. Further, they have very limited power supply. Therefore, data reconstruction algorithms, which are executed in the presence of disk failure, for mobile storage systems must be performance-driven, reliability-aware, and energy-efficient. Unfortunately, existing reconstruction schemes cannot fulfill the three goals simultaneously because they largely overlooked the fact that mobile disks have much higher failure rates than stationary disks. Besides, they normally ignore energy-saving. In this paper we develop a novel reconstruction strategy, called multi-level caching-based reconstruction optimization (MICRO), which can be applied to RAID-structured mobile storage systems to noticeably shorten reconstruction times and user response times while saving energy. MICRO collaboratively utilizes storage cache and disk array controller cache to diminish the number of physical disk accesses caused by reconstruction. Experimental results demonstrate that compared with two representative algorithms DOR and PRO, MICRO reduces reconstruction times on average 20.22% and 9.34%, while saving energy no less than 30.4% and 13%, respectively.

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.

To achieve energy-conservation and prompt responses simultaneously, in this paper we propose a novel energy-saving data placement strategy, called striping-based energy-aware (SEA), which can be applied to RAID-structured storage systems to noticeably save energy while providing quick responses. Further, to illustrate the effectiveness of SEA, we implement two SEA-powered RAID-based data placement algorithms, SEA0 and SEA5, by incorporating the SEA strategy into RAID-0 and RAID-5, respectively. Extensive experimental results demonstrate that compared with three well-known data placement algorithms greedy, SP, and HP, SEAO and SEA5 reduce mean response time on average at least 52.15% and 48.04% while saving energy on average no less than 10.12% and 9.35%, respectively.

The problem of statically assigning nonpartitioned files in a parallel I/O system has been extensively investigated. A basic workload characteristic assumption of existing solutions to the problem is that there exists a strong inverse correlation between file access frequency and file size. In other words, the most popular files are typically small in size, while the large files are relatively unpopular. Recent studies on the characteristics of web proxy traces suggested, however, the correlation, if any, is so weak that it can be ignored. Hence, the following two questions arise naturally. First, can existing algorithms still perform well when the workload assumption does not hold? Second, if not, can one develop a new file assignment strategy that is immune to the workload assumption? To answer these questions, in this paper we first evaluate the performance of three well-known file assignment algorithms with and without the workload assumption, respectively. Next, we develop a novel static file assignment strategy for parallel I/O systems, called static round-robin (SOR), which is immune to the workload assumption. Comprehensive experimental results show that SOR consistently and noticeably improves the performance in terms of mean response time over the existing schemes.

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

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%.