This paper presents tools that automate the creation of domain-specific complex programmable logic devices (CPLDs), targeted for systems-on-a-chip. By tailoring full-crossbar-based CPLDs to the domains that they support, we provide results that beat fixed reconfigurable architectures by 5.5times-11.8times on average in terms of area-delay product. We also create sparse-crossbar-based CPLD architectures, using a novel switch-smoothing algorithm that makes the crossbars amenable to layout. This algorithm reduced the wire jog pitch of our largest layout from 48 to just 3, allowing for a compact very-large-scale-integration layout. These sparse-crossbar-based CPLDs require just 0.37times the area and 0.30times the delay of our full-crossbar-based CPLDs. We also address the question of how best to add resources to a CPLD in order to support future, unknown circuits, concluding that the best strategy is to add 5% to the crossbar switch density and to provide additional programmable logic arrays of the same size found in the base architecture

Many System-on-a-Chip devices would benefit from the inclusion of reprogrammable logic on the silicon die, as it can add general computing ability, provide run-time reconfigurability, or even be used for post-fabrication modifications. Also, by tailoring the logic to the SoC domain, additional area and delay gains can be achieved over current, more general reconfigurable fabrics. This paper presents our work on creating efficient CPLD architectures for SoC, including the creation of sparse crossbars, and a novel switch smoothing algorithm which makes the crossbars amenable to layout. For our largest architecture, the switch smoothing algorithm reduced the layout's wire jog pitch from 48 to just 3, allowing for a compact VLSI layout. This has helped pave the way for our sparse-crossbar based CPLDs, which require just .37x the area and .30x the delay of our full-crossbar based CPLDs.However, regardless of how efficient an architecture we develop, it is useless if it does not have enough resources to support the circuits to be implemented. We also address the question of how best to add resources to a CPLD in order to support future, unknown circuits, concluding that the best strategy is to add 5% to the crossbar switch density and to provide additional PLAs of the same size found in the base architecture.

Reconfigurable logic fills a useful niche between the flexibility provided by a processor and the performance provided by custom hardware. This work presents the creation of domain-specific CPLD architectures, a project termed Totem-CPLD (part of the larger Totem project at UW). For the scope of this work, a CPLD is a collection of PLAs connected by a full crossbar, and they are made "domain-specific" by altering the input, product term, and output capacities of the PLAs in the architecture.

Many system-on-a-chip devices would benefit from the inclusion of reprogrammable logic on the silicon die, as it can add general computing ability, provide run-time reconfigurability, or even be used for post-fabrication modifications. Also, by catering the logic to the SoC domain, additional area and delay gains can be achieved over current, more general reconfigurable fabrics. This paper presents tools that automate the creation of domain-specific CPLDs for SoC, including an architecture generator for finding appropriate architectures and a layout generator for creating efficient layouts. By tailoring CPLDs to the domains that they are supporting, we provide results that beat representative fixed architectures by 5.6/spl times/ to 11.9/spl times/ on average in terms of area-delay product.

Parity-encoded redundant disk arrays provide highly reliable, cost-effective secondary storage with high performance for reads and large writes. Their performance on small writes, however, is much worse than mirrored disks—the traditional, highly reliable, but expensive organization for secondary storage. Unfortunately, small writes are a substantial portion of the I/O workload of many important, demanding applications such as on-line transaction processing. This paper presents parity logging , a novel solution to the small-write problem for redundant disk arrays. Parity logging applies journalling techniques to reduce substantially the cost of small writes. We provide detailed models of parity logging and competing schemes—mirroring, floating storage, and RAID level 5—and verify these models by simulation. Parity logging provides performance competitive with mirroring, but with capacity overhead close to the minimum offered by RAID level 5. Finally, parity logging can exploit data caching more effectively than all three alternative approaches.

Parity encoded redundant disk arrays provide highly reliable, cost effective secondary storage with high performance for read accesses and large write accesses. Their performance on small writes, however, is much worse than mirrored disks—the traditional, highly reliable, but expensive organization for secondary storage. Unfortunately, small writes are a substantial portion of the I/O workload of many important, demanding applications such as on-line transaction processing. This paper presents parity logging, a novel solution to the small write problem for redundant disk arrays. Parity logging applies journalling techniques to substantially reduce the cost of small writes. We provide a detailed analysis of parity logging and competing schemes—mirroring, floating storage, and RAID level 5— and verify these models by simulation. Parity logging provides performance competitive with mirroring, the best of the alternative single failure tolerating disk array organizations. However, its overhead cost is close to the minimum offered by RAID level 5. Finally, parity logging can exploit data caching much more effectively than all three alternative approaches.

We describe and evaluate a strategy for declustering the parity encoding in a redundant disk array. This declustered parity organization balances cost against data rehability and performance during failure recovery in highly-available parity-based arrays for use in continuous-operation systems. It improves on standard parity organizations by reducing the additional load on surviving disks during the reconstruction of a failed disk's contents. This yields higher user throughput during recovery, and/or shorter recovery time. We first demonstrate a software implementation of declustered parity based on balanced incomplete and complete block designs. This implementation is then evaluated using a disk array simulator under a highly concurrent workload comprised of small user accesses. We show that declustered parity penalizes user response time while a disk is being repaired (before and during its recovery) less than comparable non-declustered (RAID 5) organizations without any penalty to user response time in the fault-free state. We then show that previously proposed modifications to a simple, single-sweep reconstruction algorithm further decrease user response times during recovery, but, contrary to previous suggestions, this may be achieved at the cost of slower recovery in many declustered parity arrays. This result arises from the simple model of disk access performance used in previous work, which did not consider throughput variations due to positioning delays.