Stuttering -- characterized by involuntary disfluencies such as blocks, prolongations, and repetitions -- is often misinterpreted by automatic speech recognition (ASR) systems, resulting in elevated word error rates and making voice-driven technologies inaccessible to people who stutter. The variability of disfluencies across speakers and contexts further complicates ASR training, compounded by limited annotated stuttered speech data. In this paper, we investigate fine-tuning ASRs for stuttered speech, comparing generalized models (trained across multiple speakers) to personalized models tailored to individual speech characteristics. Using a diverse range of voice-AI scenarios, including virtual assistants and video interviews, we evaluate how personalization affects transcription accuracy. Our findings show that personalized ASRs significantly reduce word error rates, especially in spontaneous speech, highlighting the potential of tailored models for more inclusive voice technologies.

Dena Mujtaba, Nihar Mahapatra, Megan Arney, J Yaruss, Hope Gerlach-Houck, Caryn Herring, Jia Bin. Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2024.

Computerized-adaptive testing (CAT) is a form of assessment in which items/questions are administered based upon a test taker's ability (i.e., their estimated proficiency, such as a knowledge, skill, or personality characteristic). CAT is regularly used in psychological studies, medical exams, and standardized testing to reduce test length and improve measurement accuracy and precision. A key challenge in CAT is item selection. Past algorithms have been designed based on criteria such as item difficulty and maximum Fisher information. However, these only consider a fixed-length test, which may result in it being longer or less precise. To address this problem, we formulate a new multi-objective optimization problem to model the trade-off between test length and precision. A binary population-based genetic algorithm, NSGA-II, is used to obtain the set of Pareto-optimal solutions by maximizing precision and minimizing the number of questions. We evaluate our approach with a simulated study using four standard personality assessments. We also investigate the influence of test response types (e.g., binary versus categorical response) and number of variables (i.e., the number of possible items) on performance. The results obtained show multi-objective optimization can be used in CAT to minimize overall test length and improve measurement precision and overall accuracy.

Over the past few years, machine learning and AI have become increasingly common in human resources (HR) applications, such as candidate screening, resume parsing, and employee attrition and turnover prediction. Though AI assists in making these tasks more efficient, and seemingly less biased through automation, it relies heavily on data created by humans, and consequently can have human biases carry over to decisions made by a model. Several studies have shown biases in machine learning applications such as facial recognition and candidate ranking. This has spurred active research on the topic of fairness in machine learning over the last five years. Several toolkits to mitigate biases and interpret black box models have been developed in an effort to promote fair algorithms. This paper presents an overview of fairness definitions, methods, and tools as they relate to recruitment and establishes ethical considerations in the use of machine learning in the hiring space.

BACKGROUND: Accurately predicting the binding affinities of large sets of protein-ligand complexes is a key challenge in computational biomolecular science, with applications in drug discovery, chemical biology, and structural biology. Since a scoring function (SF) is used to score, rank, and identify drug leads, the fidelity with which it predicts the affinity of a ligand candidate for a protein's binding site has a significant bearing on the accuracy of virtual screening. Despite intense efforts in developing conventional SFs, which are either force-field based, knowledge-based, or empirical, their limited predictive power has been a major roadblock toward cost-effective drug discovery. Therefore, in this work, we present novel SFs employing a large ensemble of neural networks (NN) in conjunction with a diverse set of physicochemical and geometrical features characterizing protein-ligand complexes to predict binding affinity. RESULTS: We assess the scoring accuracies of two new ensemble NN SFs based on bagging (BgN-Score) and boosting (BsN-Score), as well as those of conventional SFs in the context of the 2007 PDBbind benchmark that encompasses a diverse set of high-quality protein families. We find that BgN-Score and BsN-Score have more than 25% better Pearson's correlation coefficient (0.804 and 0.816 vs. 0.644) between predicted and measured binding affinities compared to that achieved by a state-of-the-art conventional SF. In addition, these ensemble NN SFs are also at least 19% more accurate (0.804 and 0.816 vs. 0.675) than SFs based on a single neural network that has been traditionally used in drug discovery applications. We further find that ensemble models based on NNs surpass SFs based on the decision-tree ensemble technique Random Forests. CONCLUSIONS: Ensemble neural networks SFs, BgN-Score and BsN-Score, are the most accurate in predicting binding affinity of protein-ligand complexes among the considered SFs. Moreover, their accuracies are even higher when they are used to predict binding affinities of protein-ligand complexes that are related to their training sets.

BACKGROUND: Molecular docking is a widely-employed method in structure-based drug design. An essential component of molecular docking programs is a scoring function (SF) that can be used to identify the most stable binding pose of a ligand, when bound to a receptor protein, from among a large set of candidate poses. Despite intense efforts in developing conventional SFs, which are either force-field based, knowledge-based, or empirical, their limited docking power (or ability to successfully identify the correct pose) has been a major impediment to cost-effective drug discovery. Therefore, in this work, we explore a range of novel SFs employing different machine-learning (ML) approaches in conjunction with physicochemical and geometrical features characterizing protein-ligand complexes to predict the native or near-native pose of a ligand docked to a receptor protein's binding site. We assess the docking accuracies of these new ML SFs as well as those of conventional SFs in the context of the 2007 PDBbind benchmark dataset on both diverse and homogeneous (protein-family-specific) test sets. Further, we perform a systematic analysis of the performance of the proposed SFs in identifying native poses of ligands that are docked to novel protein targets. RESULTS AND CONCLUSION: We find that the best performing ML SF has a success rate of 80% in identifying poses that are within 1 Å root-mean-square deviation from the native poses of 65 different protein families. This is in comparison to a success rate of only 70% achieved by the best conventional SF, ASP, employed in the commercial docking software GOLD. In addition, the proposed ML SFs perform better on novel proteins that they were never trained on before. We also observed steady gains in the performance of these scoring functions as the training set size and number of features were increased by considering more protein-ligand complexes and/or more computationally-generated poses for each complex.

Accurately predicting the binding affinities of large diverse sets of protein-ligand complexes efficiently is a key challenge in computational biomolecular science, with applications in drug discovery, chemical biology, and structural biology. Since a scoring function (SF) is used to score, rank, and identify potential drug leads, the fidelity with which it predicts the affinity of a ligand candidate for a protein's binding site has a significant bearing on the accuracy of virtual screening. Despite intense efforts in developing conventional SFs, which are either force-field based, knowledge-based, or empirical, their limited predictive accuracy has been a major roadblock toward cost-effective drug discovery. Therefore, in this work, we explore a range of novel SFs employing different machine-learning (ML) approaches in conjunction with a variety of physicochemical and geometrical features characterizing protein-ligand complexes. We assess the scoring accuracies of these new ML SFs as well as those of conventional SFs in the context of the 2007 and 2010 PDBbind benchmark datasets on both diverse and protein-family-specific test sets. We also investigate the influence of the size of the training dataset and the type and number of features used on scoring accuracy. We find that the best performing ML SF has a Pearson correlation coefficient of 0.806 between predicted and measured binding affinities compared to 0.644 achieved by a state-of-the-art conventional SF. We also find that ML SFs benefit more than their conventional counterparts from increases in the number of features and the size of training dataset. In addition, they perform better on novel proteins that they were never trained on before.

Accurately predicting the binding affinities of large sets of protein-ligand complexes efficiently is a key challenge in computational biomolecular science, with applications in drug discovery, chemical biology, and structural biology. Since a scoring function (SF) is used to score, rank, and identify drug leads, the fidelity with which it predicts the affinity of a ligand candidate for a protein's binding site has a significant bearing on the accuracy of virtual screening. Despite intense efforts in developing conventional SFs, which are either force-field based, knowledge-based, or empirical, their limited ranking accuracy has been a major roadblock toward cost-effective drug discovery. Therefore, in this work, we explore a range of novel SFs employing different machine-learning (ML) approaches in conjunction with a variety of physicochemical and geometrical features characterizing protein-ligand complexes. We assess the ranking accuracies of these new ML-based SFs as well as those of conventional SFs in the context of the 2007 and 2010 PDBbind benchmark data sets on both diverse and protein-family-specific test sets. We also investigate the influence of the size of the training data set and the type and number of features used on ranking accuracy. Within clusters of protein-ligand complexes with different ligands bound to the same target protein, we find that the best ML-based SF is able to rank the ligands correctly based on their experimentally determined binding affinities 62.5 percent of the time and identify the top binding ligand 78.1 percent of the time. For this SF, the Spearman correlation coefficient between ranks of ligands ordered by predicted and experimentally determined binding affinities is 0.771. Given the challenging nature of the ranking problem and that SFs are used to screen millions of ligands, this represents a significant improvement over the best conventional SF we studied, for which the corresponding ranking performance values are 57.8 percent, 73.4 percent, and 0.677.

Accurately predicting the binding affinities of large sets of protein-ligand complexes is a key challenge in computational biomolecular science, with applications in drug discovery, chemical biology, and structural biology. Since a scoring function (SF) is used to score, rank, and identify drug leads, the fidelity with which it predicts the affinity of a ligand candidate for a protein's binding site has a significant bearing on the accuracy of virtual screening. Despite intense efforts in developing conventional SFs, which are either force-field based, knowledge-based, or empirical, their limited predictive power has been a major roadblock toward cost-effective drug discovery. Therefore, in this work, we explore a range of novel SFs employing different machine-learning (ML) approaches in conjunction with physicochemical features characterizing protein-ligand complexes. We assess the scoring accuracies of these new ML-based SFs as well as those of conventional SFs in the context of the 2007 PDBbind benchmark dataset on both diverse and protein-family-specific test sets. We find that the best performing ML-based SF has a Pearson's correlation coefficient of 0.771 between predicted and measured binding affinities compared to 0.644 achieved by a state-of-the-art conventional SF.

Iterative-deepening cost-bounded tree search algorithms that either require memory on the order of the search tree depth (e. g., IDA*, DFS*, etc.) or that use the entire available memory (e. g., MREC) have been proposed as viable means to solve discrete optimization problems (DOP) on which best-first branch-and-bound (BFBB) may potentially run out of memory. But, such limited-memory cost-bounded search algorithms can bear a huge overhead relative to BFBB due to re-expanding nodes with cost less than C* (essential nodes), equal to C* (boundary nodes) and/or exceeding C* (non-essential nodes) where C* denotes the cost of an optimal solution. Our contributions in this paper are two fold. First, we propose a novel available-memory non-minimal cost-bounded search method (AM-NCBS KBEST) that tries to minimize the search overhead on a single problem instance by striking a trade-off between essential node re-expansion and non-essential node expansion depending upon the value of a cost bound choice parameter ' K'. We show that this new strategy reduces the search overhead of the previous best available-memory costbounded search strategy by at least half even for the most conservative values of ' K'. Next, we present a learning-based approach (AM-NCBS KLEARN) to intelligently predict nonminimal cost-bounds for solving a new problem instance by analyzing various cost bound choices that when used over the course of the search, on a number of previously solved instances, result in the least cumulative overhead on an average. We demonstrate on a set of 100 problem instances that the learning based approach further reduces AM-NCBS KBEST's overhead that may ensue due to bad choices of 'K'.

Higher-than-normal wire temperatures and temperature gradients between the sending and receiving ends of a wire that are caused due to Joule heating and substrate hotspots affect the propagation delay of a wire significantly. In this paper, we develop a high-level model to track wire temperatures and delay variability during early stage design exploration. Results using our model show that ALU result bus wires in a 4-issue processor are likely to reach temperatures as high as 103°C (117°C) in 130-nm (45-nm) technology which is greater than the 100°C maximum normally assumed during interconnect design. For a 130-nm processor with no power and thermal management, the temperature-induced timing violations in the ALU result bus, on average across ten SPEC CPU2K benchmarks, is 2.27 per hundred bus references and it can be as high as 4.91 per hundred bus references in some programs. It increases to an average of 6.20 per hundred bus references for the same processor at the 45-nm technology node.

Modern microprocessors feature wide datapaths to support large on-chip memory and to enable computation on large-magnitude operands. With device scaling and rising clock frequencies, energy consumption and power density have become critical concerns, especially in datapath circuits. Datapaths are typically designed to optimize delay for worst-case operands. However, such operands rarely occur; the most frequently occurring input operand words (comprising long strings or subwords of 0's and 1's) present two major opportunities for energy optimization: (1) avoiding unnecessary computation involving such "special" input operand subword values and (2) exploiting timing slack in circuits (designed to accommodate worst-case inputs) arising due to such values. Previous techniques have exploited only one or the other of these factors, but not both simultaneously. Our new technique, dynamic multi-VDD, which is capable of dynamically switching between supply voltages in hardware submodules, simultaneously exploits both factors. Using the computation bypass framework and multiple supply voltages, we estimate data-dependent slack based on submodules that will be bypassed and exploit this slack by operating active submodules at a lower supply voltage. Our analysis of SPEC CPU2K benchmarks shows energy savings of up to 55% (and 46.53% on average) in functional units with minimal performance overheads

In this paper, we present a technique that exploits the statistical behavior of data values transmitted on global signal buses to determine an energy-efficient ordering of bits that minimizes the inter-wire coupling energy and also reduces total bus energy. Statistics are collected for instruction and data bus traffic from eight SPEC CPU2K benchmarks and an optimization problem is formulated and solved optimally using a publicly-available tool. Results obtained using the optimal bit order on large non-overlapping test samples from the same set of benchmarks show that, on average, adjacent inter-wire coupling energies reduce by about 35.4% for instruction buses and by about 21.6% for data buses using the proposed technique

Interconnect area and energy dissipation are critical factors in any system designed today. In this work, we present techniques to help reduce area/cost and energy dissipation of address buses with significant temporal redundancy. We describe two encoding techniques for such buses, called pattern adjuster (PA) encoding and dynamic charge/discharge encoding (DCDE), that use simple hardware and no extra bus lines for control signals. Results show that, using PA encoding, self energy reduces by 18-38%, coupling toggle energy by 19-96%, and coupling charge/discharge energy by 14-40%. In addition, with DCDE applied on top of PA, coupling charge/discharge energy reduces by up to 48%. Overall, up to 25% address bus energy savings can be obtained using our techniques compared to the energy dissipation of the original bus, with 26-79% reduction in the number of bus lines. Our techniques use very simple hardware and will have negligible encoding/decoding latencies that are much lower than those of low-power bus encoding schemes.

The influence of interconnects on processor performance and cost is becoming increasingly pronounced with technology scaling. In this paper, we present a fast compression scheme that exploits the spatial and temporal locality of addresses to dynamically compress them to different extents depending upon the extent to which they match the higher-order portions of recently-occurring addresses saved in a very small "compression cache" of capacity less than 500 bits. When a maximal match occurs, the address is compressed to the maximum extent and is transmitted on a narrow bus in one cycle. When a partial match occurs, one or more extra cycles are required for address transmission depending upon the extent of the partial match. To minimize this transmission cycle penalty (TCP), we use an efficient algorithm to determine the optimal set of partial matches to be supported in our partial match compression (PMC) scheme - we refer to this scheme as performance-optimized PMC (PO-PMC). A previously-proposed scheme called bus expander (BE) supports only a single, fixed-size match for compression. We show that all addresses that result in (maximal) matches in BE also result in the same in PMC, but the remaining addresses that are considered "no matches" in BE frequently result in partial matches in PMC, thus helping curtail the latter's TCP significantly. Across many SPEC CPU2000 integer and floating-point benchmarks, we find that average program performance improves by 3% when using PO-PMC compared to that when using BE. Further, we investigate how area slack arising from compression can be exploited for bus latency improvement by increasing inter-wire spacing. We find that, on the average, it can reduce bus latency by up to 84.63% and thereby improve program performance by about 16%.

Soft errors are changes in logic state of a circuit/system resulting from the latching of single-event transients (transient voltage fluctuations at a logic node or SETs) caused by high-energy particle strikes or electrical noise. Due to technology scaling and reduced supply voltages, they are expected to increase by several orders of magnitude in logic circuits. In this work, we present a very efficient and systematic approach to cope with soft errors in combinational and sequential logic circuits. The features and merits of our approach are: (1) use of error masking in non-critical paths along with error detection and recovery in critical paths, which substantially lowers overhead for error correction; (2) average 93% soft-error rate (SER) reduction as SETs of width approximately half the clock period time can be tolerated; (3) area and power overheads can be traded-off with SER reduction based on application requirements. We also present two additional techniques to more aggressively utilize slack in circuits and further improve SER reduction by: (1) exploiting circuit delay dependence on input vectors and (2) redistributing slack in pipelined circuits.

Soft errors are functional failures resulting from the latching of single-event transients (transient voltage fluctuations at a logic node or SETs) caused by high-energy particle strikes or electrical noise. Due to technology scaling and reduced supply voltages, they are expected to increase by several orders of magnitude in logic circuits. Both combinational and sequential logic circuits are expected to be affected. Many different latch designs to prevent soft errors due to particle strikes on the latch nodes have been proposed. We review these designs and compare them based on their robustness and their power and performance overheads. We also propose new latch designs, the best of which is vulnerable only to a single-event, multiple-upset without any delay overhead and consumes only 40% power of a standard latch. We expect this work will help designers to select latches for applications where soft error is an important design metric.

In this paper, we review three different families of delay elements used in CMOS VLSI design: (1) transmission gate based, (2) cascaded inverter based, and (3) voltage-controlled ones. We compare their effectiveness in terms of yield, which is defined as the number of delay elements that have delays within a specified delay range. The delay variations are obtained through HSpice Monte Carlo simulations and are analyzed using analytical delay expressions. The sensitivity of the delay elements to different process and environmental variations can be studied using the simulation results. This will enable designers to select the best delay element for their design and also do a robust design by taking into account the sensitivities of delay elements to different parameters.

Technology scaling and rising clock frequencies have made active and leakage power and power density major concerns. Traditional power-reduction techniques, such as dynamic voltage scaling, multi-VDD, gated-VDD, and multi-threshold designs, exploit the slack available in non-critical operations/modes and non-critical areas of the circuit. This limits the amount of power reduction when the circuit is balanced or the critical path dominates the power consumption. We present a systematic technique in which time borrowing (TB) (or slack passing) is used to enhance the effectiveness of such traditional low-power techniques that exploit the timing characteristics of a circuit. This is in addition to TB done for performance or even when TB opportunities for performance do not exist. We also propose non-uniform TB, in which not all primary output gates of a pipeline stage borrow equal amounts of time, to reduce power when TB for performance cannot be done. Two ways to distribute slack for low-power operation in a pipeline circuit are discussed and the effectiveness of TB for low-power is demonstrated using a high-performance 32-bit enhanced multiple output domino logic adder and an 8 x 8 Wallace tree multiplier. Slack redistribution improves the energy savings obtained using traditional low-power techniques as follows: maximum 22% and average 19% extra active energy savings for the adder and maximum 45% and average 37% extra sub-threshold leakage power savings for the multiplier.

With technology scaling, power dissipation and localized heating in global and semi-global bus wires are becoming increasingly important, and this necessitates the development of accurate models to explore these effects during design stage, with simulators and using realistic workloads. In this work, we present a unified nanometer-scale bus energy dissipation and thermal model that helps designers monitor energy dissipation and temperature rise in individual wires during dynamic simulation. In addition to self capacitance, our model incorporates the effects of capacitive coupling between adjacent as well as non-adjacent pairs of wires on switching energy, effect of repeater insertion, and the effect of lateral heat transfer between adjacent wires, all of which have been ignored in earlier models. Next, using our integrated model in a first-of-its-kind study, we study energy dissipation and thermal characteristics of instruction and data address buses with traces obtained from standard SPEC CPU2000 benchmarks and using technology parameters for various nanometer technology nodes from the ITRS road-map. We also evaluate the effect of some well-known low-power bus design schemes on bus line energy dissipation.

Soft errors are the functional failures resulting from the latching of single-event transients (transient voltage fluctuations at a logic node or SETs) caused by high-energy particle strikes or electrical noise. Traditionally, they have been deemed to be a problem in memory structures, for which effective techniques (such as error correcting codes) are well known. However, due to technology scaling and reduced supply voltages, they are expected to increase by several orders of magnitude in logic circuits. Existing circuit and architectural approaches to addressing soft errors in logic circuits have appreciable area/cost, performance, and/or energy overheads or are limited to particular types of circuits (combinational or sequential). We present a very efficient and systematic error masking technique that uses the same circuitry to cope with soft errors in combinational and sequential circuits. It prevents an SET pulse of width less than approximately half of the slack available in the propagation path from latching and turning into a soft error. The SET is masked without additional delay and within the clock cycle time in an area- and energy-efficient manner, which makes this technique attractive for commodity as well as reliability-critical applications. Our technique also tolerates soft errors in the overhead circuitry, which we minimize through clustering. Application of our technique to ISCAS85 benchmark circuits yields an average SER reduction of 70.93% with an average area overhead of only 11.98%.

Dynamic address compression schemes that exploit address locality can help reduce both address bus energy and cost simultaneously with only a small performance penalty. In this work, we investigate two such schemes and determine their optimal parameters that result in the highest area/cost reductions and least performance penalty for various address buses (both on- and off-chip) in current systems. For addresses compressed with these schemes, we study energy reduction of buses in current and future nanometer technology nodes. Our study uses the cycle-accurate simulator for the Alpha 21264 processor called sim-alpha for performance estimation and accurate interconnect models considering inter-wire capacitances for bus energy estimation. Results show that using address compression results in only small performance overheads (less than 1% for compressing a 38-bit bus to 14 bits) and reduce bus energy dissipation by as much as 13% when applied to on-chip buses in current technologies.

We analyze three different techniques, namely, memoing (caching results that can be reused), narrow-width operand exploitation (limiting computation to low order bytes), and byte encoding (computation performed over significant bytes) that dynamically exploit operands to lower power consumption in integer function units. Previously, estimates of power savings based on switching activity were reported. Our implementation of integer function units (CLA, array multiplier, comparator, etc.) at the VLSI level and analysis using standard integer benchmarks from the SPEC CPU2000 suite provide realistic power savings and area and delay overheads.

Minimizing the area/cost and power consumption of communication components (address, instruction, and data buses and associated hardware like I/O pins, pads, and buffers) is becoming important in modern microprocessors. Currently, utilization of buses is not taken into account during design of many bus systems. This may lead to underutilization of many buses during actual operation. We propose a scheme that exploits the underutilization of address buses to result in a cost-effective and energy-efficient bus system design. This is accomplished by using buses of narrow width, new encoding schemes for narrow buses, and with design of hardware that result in only a minimal impact on performance and power consumption. We show the efficacy of our schemes using simulations on a validated Alpha 21264 model for SimpleScalar and using physical address traces from 14 SPEC CPU2000 benchmarks.

The continuing exponential growth in processor performance, combined with technology, architecture, and application trends, places enormous demands on the memory system to allow information storage and exchange at a high-enough performance (i.e., to provide low latency and high bandwidth access to large amounts of information), at low power, and cost-effectively. The paper comprehensively analyzes the redundancy in the information (addresses, instructions, and data) stored and exchanged between the processor and the memory system and evaluates the potential of compression in improving performance, power consumption, and cost of the memory system. Traces obtained with Sun Microsystems' simulator simulating SPARC executables of nine integer and six floating-point programs in the SPEC CPU2000 benchmark suite and analyzed using Markov entropy models, existing compression schemes, and CACTI 3.0 and SimplePower timing, power, and area models yield impressive results.

This paper presents a new framework called gate triggering for systematically minimizing glitch power dissipation in static CMOS ICs. It is based on the idea that glitches can be effectively minimized by triggering logic evaluation at a gate only when all of its inputs have stablized. For this purpose, to every potentially glitchy gate (or a suitable subset of such gates) is added a small amount of control logic, which, when enabled triggers logic evaluation at the gate. A clocked delay chain is employed to generate enable signals at the proper times for all gates to be triggered. We present six specific techniques based on gate triggering that differ in the type of control logic and the way it is used to control a gate. These techniques have varying effectiveness and area and timing overheads, which we analyze in detail. Application of these techniques to test circuits yields promising results.

Structural fault tolerance (SFT) is the ability of a multiprocessor to reconfigure around faulty processors or links in order to preserve its original processor interconnection structure; In this paper, we focus on the design of SFT multiprocessors that have low switch and link overheads, but can tolerate a very large number of processor faults on the average. Most previous work has concentrated on deterministic k-fault-tolerant (k-FT) designs in which exactly k spare processors and some spare switches and links are added to construct multiprocessors that can tolerate any k processor faults. However, after k faults are reconfigured around, much of the extra links and switches can remain unutilized. It is possible within the basic node-covering framework, which was introduced by Dutt and Hayes as an efficient k-FT design method, to design FT multiprocessors that have the same amount of switches and links as, say, a two-FT deterministic design, but have s spare processors, where s/spl Gt/2, so that, on the average, k=/spl Theta/(s) (k/spl les/s) processor failures can be reconfigured around. Such designs utilize the spare link and switch capacity very efficiently, and are called probabilistic FT designs. An elegant and powerful method to construct covering graphs or CG's, which are key to obtaining the probabilistic FT designs, is to use linear error-correcting codes (ECCs). We show how to construct probabilistic designs with very high average fault tolerance but low wiring and switch overhead using ECCs like the 2D-parity, full-two, 3D-parity, and full-three codes.

For many applications of the A* algorithm, the state space is a graph rather than a tree. The implication of this for parallel A* algorithms is that different processors may perform significant duplicated work if interprocessor duplicates are not pruned. In this paper, we consider the problem of duplicate pruning in parallel A* graph-search algorithms implemented on distributed-memory machines. A commonly used method for duplicate pruning uses a hash function to associate with each distinct node of the search space a particular processor to which duplicate nodes arising in different processors are transmitted and thereby pruned. This approach has two major drawbacks. First, load balance is determined solely by the hash function. Second, node transmissions for duplicate pruning are global; this can lead to hot spots and slower message delivery. To overcome these problems, we propose two different duplicate pruning strategies: 1) To achieve good load balance, we decouple the task of duplicate pruning from load balancing, by using a hash function for the former and a load balancing scheme for the latter. 2) A novel search-space partitioning scheme that allocates disjoint parts of the search space to disjoint subcubes in a hypercube (or disjoint processor groups in the target architecture), so that duplicate pruning is achieved with only intrasubcube or adjacent intersubcube communication. Thus message latency and hot-spot probability are greatly reduced. The above duplicate pruning schemes were implemented on an nCUBE2 hypercube multicomputer to solve the Traveling Salesman Problem (TSP). For uniformly distributed intercity costs, our strategies yield a speedup improvement of 13 to 35 percent on 1,024-processors over previous methods that do not prune any duplicates, and 13 to 25 percent over the previous hashing-only scheme. For normally distributed data the corresponding figures are 135 percent and 10 to 155 percent. Finally, we analyze the scalability of our parallel A* algorithms on k-ary n-cube networks in terms of the isoefficiency metric, and show that they have isoefficiency lower and upper bounds of /spl Theta/(P log P) and /spl Theta/(Pkn/sup 2/), respectively.