Structural health monitoring (SHM), which is the process of gauging the health of instrumented structures, is becoming increasingly important as much of the world's transportation infrastructure ages and deteriorates. Wireless sensor networks (WSNs) have the potential to deliver continuous SHM at a low cost. We present a novel WSN system that monitors ambient structural vibrations and looks for deviations from a baseline response to assess the condition of the structure under observation. Efficiency is achieved by implementing our damage assessment process with an innovative wireless-sensor-based technique involving look-up tables. By using look-up tables we are able to minimize computations. Only 4-6 integer and two floatingpoint operations are required per damage assessment. This is in contrast to the majority of other methods that rely on precise engineering models of the monitored structures. Our look-up table technique is benchmarked against the brute force approach, which involves solving equations, by measuring the execution time of each implementation on a low-power Microchip microcontroller. Here, we were able to achieve a speedup of roughly five. In addition, we investigate a tradeoff between average transmission power and the number of measurements required to make a decision as to the structure's condition. Finally, we benchmark our damage assessment process using a case study to verify its efficacy for bridges.

Vector coprocessors (VPs), commonly being assigned exclusively to a single thread/core, are not often performance and energy efficient due to mismatches with the vector needs of individual applications. We present in this article an easy-to-implement VP virtualization technique that, when applied, enables a multithreaded VP to simultaneously execute multiple threads of similar or arbitrary vector lengths to achieve improved aggregate utilization. With a vector register file (VRF) virtualization technique invented to dynamically allocate physical vector registers to threads, our VP virtualization approach improves programmer productivity by providing at runtime a distinct physical register name space to each competing thread, thus eliminating the need to solve register-name conflicts statically. We applied our virtualization technique to a multithreaded VP and prototyped an FPGA-based multicore processor system that supports VP sharing as well as power gating for better energy efficiency. Under the dynamic creation of disparate threads, our benchmarking results show impressive VP speedups of up to 333% and total energy savings of up to 37% with proper thread scheduling and power gating compared to a similar-sized system that allows VP access to just one thread at a time.

For multicore processors with a private vector coprocessor (VP) per core, VP resources may not be highly utilized due to limited data-level parallelism (DLP) in applications. Also, under low VP utilization static power dominates the total energy consumption. We enhance here our previously proposed VP sharing framework for multicores in order to increase VP utilization while reducing the static energy. We describe two power-gating (PG) techniques to dynamically control the VP's width based on utilization figures. Floating-point results on an FPGA prototype show that the PG techniques reduce the energy needs by 30-35 percent with negligible performance reduction as compared to a multicore with the same amount of hardware resources where, however, each core is attached to a private VP.

Vector coprocessor (VP) resources are often underutilized due to the lack of sustained DLP (data-level parallelism) or the presence of vector-length variations in application code. Our work is motivated by: a) the omnipresence of vector operations in high-performance scientific and embedded applications, b) the need for performance and energy efficiency, and c) applications that must often handle various vector sizes. Our design for VP sharing in multicores enhances performance while maintaining low area and energy costs. Our 40nm ASIC design yields 16.66 GFLOPs/Watt. Also, a detailed clock and power gating analysis further proves the viability of our approach.

Floating-point square root is a fundamental operation in signal processing and various HPC applications. Since this is an expensive operation in resource and energy consumption, its efficient implementation should be of priority in future multicores that will face dark silicon issues. This paper presents a low-cost, low-power consumption design to calculate the square root using the IEEE754 single-precision floating-point format. Two versions of the design are investigated with and without clock gating (CG), respectively. Evaluation involves FPGA and ASIC technologies at 40 and 65 nm. Substantial performance growth and reduced power consumption are gained as compared to a popular iterative solution. The ASIC design demonstrates much lower power consumption, which at 40 nm is lower than that at 65 nm by about a threefold. At 40 nm, CG for the ASIC realization is justified primarily for low activity rates.

For most of the applications that make use of a dedicated vector coprocessor, its resources are not highly utilized due to the lack of sustained data parallelism which often occurs due to vector-length variations in dynamic environments. The motivation of our work stems from: (a) the mandate for multicore designs to make efficient use of on-chip resources for low power and high performance; (b) the omnipresence of vector operations in high-performance scientific and emerging embedded applications; (c) the need to often handle a variety of vector sizes; and (d) vector kernels in application suites may have diverse computation needs. We present a robust design framework for vector coprocessor sharing in multicore environments that maximizes vector unit utilization and performance at substantially reduced energy costs. For our adaptive vector unit, which is attached to multiple cores, we propose three basic shared working policies that enforce coarse-grain, fine-grain, and vector-lane sharing. We benchmark these vector coprocessor sharing policies for a dual-core system and evaluate them using the floating-point performance, resource utilization, and power/energy consumption metrics. Benchmarking for FIR filtering, FFT, matrix multiplication, and LU factorization shows that these coprocessor sharing policies yield high utilization and performance with low energy costs. The proposed policies provide 1.2--2 speedups and reduce the energy needs by about 50% as compared to a system having a single core with an attached vector coprocessor. With the performance expressed in clock cycles, the sharing policies demonstrate 3.62--7.92 speedups compared to optimized Xeon runs. We also introduce performance and empirical power models that can be used by the runtime system to estimate the effectiveness of each policy in a hybrid system that can simultaneously implement this suite of shared coprocessor policies.

On behalf of the organizing committees, we welcome you to the 24th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2012) held in Athens, Greece. We greatly appreciate the authors for their outstanding paper contributions and we thank them in advance for their participation. We also value the time spent by the area chairs and program committee members for paper evaluation efforts and really making sure that ICTAI 2012 will be a great success.

Protecting on-chip cache memories against soft errors has become an increasing challenge in designing new generation reliable microprocessors. Previous efforts have mainly focused on improving the reliability of the cache data arrays. Due to its crucial importance to the correctness of cache accesses, the tag array also demands high reliability against soft errors. Exploiting the address locality of memory accesses, we propose to duplicate most recently accessed tag entries in a small tag replication buffer (TRB) thus to protect the information integrity of the tag array in the data cache. Experimental results show that our proposed TRB scheme achieves a high 90% access-with-replica (AWR) rate with low performance (~0%), energy (16.3%), and area (19.9%) overheads. We also conduct a detailed design space exploration for the TRB design and propose a selective TRB scheme that achieves a higher AWR rate (97.4%) for the dirty cachelines with negligible overheads. To provide a comprehensive evaluation of the tag-array reliability, we further conduct an architectural vulnerability factor (AVF) analysis for the tag array in the data cache and propose a refined metric, detected-without-replica-AVF (DOR-AVF), which combines the AVF and AWR analysis. Based on our DOR-AVF analysis, a selective TRB scheme with early write-back (S-TRB-EWB) is proposed, which achieves a zero DOR-AVF and 100% AWR rate at a negligible performance overhead. Results from statistical fault/error injection experiment also confirm the effectiveness of our TRB schemes and the achieved reliability of the cache tag array that recovers 100% of detected errors.

For most of the applications that make use of a vector coprocessor, the resources are not highly utilized due to the lack of sustained data parallelism, which sometimes occurs due to vector-length changes in dynamic environments. The motivation of our work stems from (a) the mandate for multicore designs to make efficient use of the on-chip resources, (b) the frequent presence of vector operations in high-performance scientific and embedded applications, (c) the increased probability that different cores may deal with different vector lengths at various times, and (d) different vector kernels in the same or different application suites may have diverse computation needs. Our objective is to provide a versatile design framework that can facilitate vector coprocessor sharing among multiple cores in a manner that maximizes resource utilization while also yielding very high performance at reduced cost. We propose three basic shared vector coprocessor architectures for multicores based on coarse-grain, fine-grain and vector lane sharing. We benchmark these distinct vector architectures for a dual-core system using the floating-point performance and resource utilization metrics. Our analysis shows that vector lane sharing, where the number of vector lanes assigned to a core can be controlled dynamically, provides the greatest flexibility and generally yields very good results. Since, however, each of the three design choices has its own performance advantages under certain vector-load conditions, we ultimately suggest a hybrid vector coprocessor design that can support all three architectural choices as per the core and application collective needs.

Real-time face recognition by computer systems is required in many commercial and security applications since it is the only way to protect privacy and security. On the other hand, face recognition generates huge amounts of data in real-time. Filtering out meaningful data from this raw data with high accuracy is a complex task. Most of the existing techniques primarily focus on the accuracy aspect using extensive matrix-oriented computations. Efficient realizations primarily reduce the computational space using eigenvalues. On the other hand, an eigenvalues oriented evaluation has minimum time complexity of O (n3), where n is the rank of the covariance matrix, the computation cost for co-variance generation is extra. Our frequency distribution curve (FDC) technique avoids matrix decomposition and other high computationally intensive matrix operations. FDC is formulated with a bias towards efficient hardware realization and high accuracy by using simple vector operations. FDC requires pattern vector (PV) extraction from an image within O (n2) time. Our enhanced FDC-based architecture proposed in this paper further shifts a computationally expensive component of FDC to the offline layer of the system, thus resulting in very fast online evaluation of the input data. Furthermore, efficient online testing is pursued as well using an adaptive controller (AC) for PV classification utilizing the Euclidian vector norm length. The pipelined AC architecture adapts to the availability of resources in the target silicon device. Our implementation on an XC5VSX50t FPGA demonstrates a high accuracy of 99% in face recognition for 400 images in the ORL database, generally requiring less than 200 nsec per image.

In any situation where a set of personal attributes are revealed, there is a chance that revealed data can be linked back to its owner. Examples of such situations are publishing user profile micro-data or information about social ties, sharing profile information on social networking sites, or revealing personal information in computer-mediated communication (CMC). Measuring user anonymity is the first step to ensuring that the identity of the owner of revealed information cannot be inferred. Most current measures of anonymity ignore important factors such as the probabilistic nature of identity inference, the inferrer's outside knowledge, and the correlation between user attributes. Furthermore, in the social computing domain, variations in personal information and various levels of information exchange among users make the problem more complicated. We present an information-entropy-based realistic estimation of the user anonymity level to deal with these issues in social computing in an effort to help predict the identity inference risks. We then address implementation issues of online protection by proposing complexity reduction methods that take advantage of basic information entropy properties. Our analysis and delay estimation based on experimental data show that our methods are viable, effective, and efficient in facilitating privacy in social computing and synchronous CMCs.

Localized heating-up creates thermal hotspots across the chip, with the integer register file ranked as the hottest unit in high-performance microprocessors. In this paper, we perform a detailed study on the thermal behavior of a low-power value-aware register file (VARF) that is subjected to internal fine-grain hotspots. To further optimize its thermal behavior, we propose and evaluate three thermal-aware control schemes, thermal sensor (TS), access counter (AC), and register-id (ID) based, to balance the access activity and thus the temperature across different partitions in the VARF. The simulation results using SPEC CINT2000 benchmarks show that the register-id controlled VARF (ID-VARF) scheme achieves optimized thermal behavior at minimum cost as compared to the other schemes. We further evaluate the performance impact of the thermal-aware VARF design with the dynamic thermal management (DTM). The experimental results show that the ID-VARF can improve the performance by 26.1% and 7.2% over the conventional register file and the original VARF design, respectively.

The performance of matching schemes for input- queued (IQ) packet switches is mainly defined by the selection policy adopted. This policy can be aimed to produce a large weight sum for matched input-output pairs, where each input- output pair is assigned a weight, or to produce a large match size in the number of matched pairs, giving place to maximum weight matching or maximum size matching, respectively. However, schedulers can only provide a single match in function of the selection (of candidate ports) policy adopted and of the backlogged traffic at the input queues. A parallel match evaluator was recently proposed to provide not one but several match options at the same time. This approach evaluates several predefined and fixed matches and picks the match with the largest size. However, the fixed permutations of the evaluated matches may produce low performance under traffic with nonuniform distributions because of the limited number of choices. This paper proposes to make the parallel match evaluator configurable and two schemes to provide diverse and changeable matches such that the matches (and therefore, the evaluator) become adaptable to the traffic pattern. The proposed schemes were tested under uniform and nonuniform traffic patterns and the results show that these schemes provide high performance, even when scheduling is performed between periods of multiple time slots, or framed intervals. The proposed approach can be used for configuring slow micro-electro-mechanical (MEM) optical switch fabrics.

A serious threat to user privacy in new mobile and Web2.0 applications stems from `social inferences'. These unwanted inferences are related to the users' identity, current location and other personal information. We have previously introduced `inference functions' to estimate the social inference risk based on information entropy. In this paper, after analyzing the problem and reviewing our risk estimation method, we create a decision tree to distinguish between high risk and normal situations. To evaluate our methodology, test and training datasets were collected during a large mobile-phone field study for a location-aware application. The classification tree employs our two inference functions, for the current and past situations, as internal nodes. Our results show that the achieved true classification rates are significantly better than approaches that employ other available features for the internal nodes of the trees. The results also suggest that common classification tools cannot accurately capture the information entropy for social applications. This is mostly due to the lack of enough training data for high-risk, low-entropy situations and outliers. Thus, we conclude that estimating the information entropy and the relevant inference risk using a pre-processor can yield a simpler and more accurate classification tree.

No abstract available.

Soft errors induced by energetic particle strikes in on-chip cache memories have become an increasing challenge in designing new generation reliable microprocessors. Previous efforts have exploited information redundancy via parity/ECC codings or cacheline duplication for information integrity in on-chip cache memories. Due to various performance, area/size, and energy constraints in various target systems, many existing unoptimized protection schemes may eventually prove significantly inadequate and ineffective. In this paper, we propose a new framework for conducting comprehensive studies and characterization on the reliability behavior of cache memories, in order to provide insight into cache vulnerability to soft errors as well as design guidance to architects for highly efficient reliable on-chip cache memory design. Our work is based on the development of new lifetime models for data and tag arrays residing in both the data and instruction caches. Those models facilitate the characterization of cache vulnerability of stored items at various lifetime phases. We then exemplify this design methodology by proposing reliability schemes targeting at specific vulnerable phases. Benchmarking is carried out to showcase the effectiveness of our approach.

Protecting the register value and its data buses is crucial to reliable computing in high-performance microprocessors due to the increasing susceptibility of CMOS circuitry to soft errors induced by high-energy particle strikes. Since the register file is in the critical path of the processor pipeline, any reliable design that increases either the pressure on the register file or the register file access latency is not desirable. In this paper, we propose to exploit narrow-width register values, which present the majority of the generated values, for making a duplicate of the value within the same data item; this in-register duplication(IRD)eliminates the requirement for additional copy registers. The data path pipeline is augmented to efficiently incorporate parity encoding and parity checking such that error recovery is seamlessly supported in IRD and the parity checking is overlapped with the execution stage to avoid increasing the critical path. A detailed architectural vulnerability factor (AVF) analysis shows that IRD significantly reduces the AVF from 8.4% in a conventional unprotected register file to 0.1% in an IRD register file. Our experimental evaluation using the SPEC CINT2000 benchmark suite also shows that IRD provides superior read-with-duplicate (RWD) and error detection/recovery rates under heavy error injection as compared to previous reliability schemes, while only incurring a small power overhead.

Soft-error induced reliability problems have become a major challenge in designing new generation microprocessors. Due to the on-chip caches' dominant share in die area and transistor budget, protecting them against soft errors is of paramount importance. Recent research has focused on the design of cost-effective reliable data caches in terms of performance, energy, and area overheads, based on the assumption of fixed error rates. However, for systems in operating environments that vary with time or location, those schemes will be either insufficient or overdesigned for the changing error rates. In this paper, we explore the design of a self-adaptive reliable data cache that dynamically adapts its employed reliability schemes to the changing operating environments thus to maintain a target reliability. The proposed data cache is implemented with three levels of error protection schemes, a monitoring mechanism, and a control component that decides whether to upgrade, downgrade, or keep the current protection level based on the feedback from the monitor. Our experimental evaluation using a set of SPEC CPU2000 benchmarks shows that our self-adaptive data cache achieves similar reliability to a cache protected by the most reliable scheme, while simultaneously minimizing the performance and power overheads.

To conserve space and power, and to incorporate dynamic adaptability in embedded systems, it is important to utilize hardware components as best as possible. The hardware customization of application kernels reduces the execution time and possibly the power consumption. Reconfiguring the same hardware to facilitate various customized kernels as execution proceeds greatly reduces the space requirements. When the kernel execution is carefully scheduled considering also the reconfiguration overheads, the obtained performance gain can offset such overheads. We present our policy and experiments of customizing and reconfiguring actual hardware for embedded benchmark kernels implemented on Field-Programmable Gate Arrays (FPGAs). The results reveal substantial performance improvement and resource conservation.

Protecting the register value and its data buses is crucial to reliable computing in high-performance microprocessors due to the increasing susceptibility of CMOS circuitry to soft errors induced by high-energy particle strikes. Since the register file is in the critical path of the processor pipeline, any reliable design that increases either the pressure on the register file or the register file access latency is not desirable. In this paper, we propose to exploit narrow-width register values, which present the majority of the generated values, for duplicating a copy of the value within the same data item, called in-register duplication (IRD), eliminating the requirement of additional copy registers. The datapath pipeline is augmented to efficiently incorporate parity encoding and parity checking such that error recovery is seamlessly supported in IRD and the parity checking is overlapped with the execution stage to avoid increasing the critical path. Our experimental evaluation using the SPEC CINT2000 benchmark suite shows that IRD provides superior read-with-duplicate (RWD) and error detection/recovery rates under heavy error injection as compared to previous reliability schemes

Field-programmable gate array (FPGA) technology is characterized by continuous improvements that provide new opportunities in system design. multiprocessors-on-a-programmable-chip (MPoPCs) represent the recent trend in this arena; they integrate the advantages of both software programmability and hardware reconfigurability. However, FPGAs consume more energy than ASICs. The lack of powerful tools and models to estimate and verify the energy consumption in the early stages of the design cycle exacerbates this problem. In this paper, we propose a system-level energy estimation model to accompany our design methodology for HERA (heterogeneous reconfigurable architecture), a versatile reconfigurable MPoPC that we have implemented on Xilinx FPGAs. The model utilizes both physical-level measurements from a hardware component library and application statistics. Experiments with the parallel LU factorization of large sparse matrices show an average error in energy estimation of about 5.17%. We also demonstrate performance-energy trade-off test cases that incorporate this model into HERA's design methodology to satisfy the real needs of application-system pairs.

The solution to a set of sparse linear equations Ax=b, where A is an n/spl times/n sparse matrix and b is an n-element vector, can be obtained using the W-matrix method. An enhanced vector processor is implemented on an FPGA for this problem. Performance results are presented. The effect of pipelined multiple functional units, multiple data buses, instruction chaining, hardware synchronization, pipelined scattering, matrix density, and distribution of non-zero elements is analyzed.

Combined input-crosspoint buffered (CICB) packet switches relax arbitration timing and provide high-performance switching. However, the amount of memory in buffered crossbars required to achieve 100% throughput under flows with high data rates is proportional to the number of ports, N, and the crosspoint buffer size k, which is defined by the distance between the line cards and the buffered crossbar. Long distances between the line cards and the buffered crossbar can make a CICB switch costly to implement. In this paper, we propose a load-balanced CICB packet switch to support long distances between the buffered crossbar and the line cards using crosspoint buffers of small size. The proposed switch reduces the required crosspoint buffer size by a factor of N and keeps the cells in sequence.

Designing temperature-aware microarchitectures for microprocessors at new technologies is becoming a critical requirement due to the exponentially increasing on-chip power density. Extremely high power density, thus the very high on-chip temperature, not only significantly increases the packaging and cooling costs, but also creates tremendous difficulties in chip leakage control and reliability. Being a major contributor to chip transistor budget and die area, caches account for a significant share of the overall processor power consumption, including both dynamic and leakage power. This work analyzes the thermal behavior of subarrays within a conventional data cache when running a set of applications from the SPEC2000 benchmark suite, and proposes two new subarraying schemes, namely, the separated scheme and the interleaved scheme, to improve the thermal behavior of subarrays in terms of more predictable behavior and reduced subarray temperatures. These optimizations can be also combined with dynamic thermal management (DTM) techniques to further improve the efficiency of thermal management. The impact of leakage control on the subarray thermal behavior is also evaluated.

FPGAs (field-programmable gate arrays) are often used as coprocessors to boost the performance of data-intensive applications (Tessier and Burleson, 2001; Wirthlin et al., 1994) ). However, mapping algorithms onto multimillion-gate FPGAs is time consuming and remains a challenge in configurable system design. The communication overhead between the host workstation and the FPGAs is also significant. To address these problems, we propose in this paper the FPGA-based hierarchical-SIMD (H-SIMD) machine with its codesign of the hierarchical instruction set architecture (HISA). At each level, HISA instructions are classified into communication instructions or computation instructions. The former are executed by the local controller while the latter are issued to the lower level for execution. Additionally, by using a memory switching scheme and the high-level HISA set to partition the application into coarse-grain tasks, the host-FPGA communication overhead can be hidden. We enlist matrix multiplication (MM) to test the effectiveness of H-SIMD. The test results show sustained high performance.

Summary form only given. The exponentially increasing complexity of many scientific applications and the high cost of supercomputing force us to explore new, sustainable, and affordable high-performance computing platforms. Recent significant advances in FPGA technology and the inherent advantages of configurable logic have brought about new research efforts in the configurable computing field: parallel processing on configurable chips. We explore here parallel LU factorization of large sparse block-diagonal-bordered (BDB) matrices on a configurable multiprocessor that we have designed and implemented. A dynamic load balancing strategy is proposed and analyzed. Performance results for IEEE power test systems are provided. Our research provides evidence that configurable logic can be a viable alternative to high-performance scientific computing.

Abstract Configurable computing, where hardware resources are configured appropriately to match specific hardware designs, has recently demonstrated its ability to significantly improve performance for a wide range of computation‐intensive applications. With steady advances in silicon technology, as predicted by Moore's Law, Field‐Programmable Gate Array (FPGA) technologies have enabled the implementation of System‐on‐a‐Programmable‐Chip (SOPC or SOC) computing platforms, which, in turn, have given a significant boost to the field of configurable computing. It is possible to implement various specialized parallel machines in a single silicon chip. In this paper, we describe our design and implementation of a parallel machine on an SOPC development board, using multiple instances of a soft IP configurable processor; we use this machine for LU factorization. LU factorization is widely used in engineering and science to solve efficiently large systems of linear equations. Our implementation facilitates the efficient solution of linear equations at a cost much lower than that of supercomputers and networks of workstations. The intricacies of our FPGA‐based design are presented along with tradeoff choices made for the purpose of illustration. Performance results prove the viability of our approach. Copyright © 2004 John Wiley & Sons, Ltd.

PC clusters have become popular in parallel processing. They do not involve specialized interprocessor networks, so the latency of data communications is rather long. The programming models for PC clusters are often different than those for parallel machines or supercomputers containing sophisticated interprocessor communication networks. For PC clusters, load balancing among the nodes becomes a more critical issue in attempts to yield high performance. We introduce a new model for program development on PC clusters, namely, the super-programming model (SPM). The workload is modeled as a collection of super-instructions (SIs). We propose that a set of SIs be designed for each application domain. They should constitute an orthogonal set of frequently used high-level operations in the corresponding application domain. Each SI should normally be implemented as a high-level language routine that can execute on any PC. Application programs are modeled as super-programs (SPs), which are coded using SIs. SIs are dynamically assigned to available PCs at runtime. Because of the known granularity of SIs, an upper bound on their execution time can be estimated at static time. Therefore, dynamic load balancing becomes an easier task. Our motivation is to support dynamic load balancing and code porting, especially for applications with diverse sets of inputs such as data mining. We apply here SPM to the implementation of an a priori-like algorithm for mining association rules. Our experiments show that the average idle time per node is kept very low.

Several driving forces have recently brought about significant advances in the field of configurable computing. They have also enabled parallel processing within a single field-programmable gate array (FPGA) chip. The ever-increasing complexity of application algorithms and the supercomputing crisis have made this new parallel-processing approach more important and pertinent. Its cost-effectiveness provides system designers with the greatest flexibility while imposing many challenges to current hardware and software codesign methodologies. This paper explores practical hardware and software design and implementation issues for FPGA-based configurable multiprocessors, based on the authors' first-hand experience with a shared-memory implementation of parallel LU factorization for sparse block-diagonal-bordered (BDB) matrices. We also propose a new dynamic load balancing strategy for parallel LU factorization on our system. Performance results are included to prove the viability of this new multiprocessor design approach.

Existing interprocessor connection networks are often plagued by poor topological properties that result in large memory latencies for distributed shared-memory (DSM) computers or multicomputers. On the other hand, scalable networks with very good topological properties are often impossible to build because of their prohibitively high very large scale integration (VLSI) (e.g. wiring) complexity. Such a network is the generalized hypercube (GH). The GH supports full connectivity of all of its nodes in each dimension and is characterized by outstanding topological properties. Also, low-dimensional GHs have very large bisection widths. We present here the class of highly-overlapping windows (HOWs) networks, which are capable of lower complexity than GHs, comparable performance and better scalability. HOWs are obtained from GHs by uniformly removing edges to produce feasible systems of lower wiring complexity. Resulting systems contain numerous highly-overlapping GHs of smaller size. The GH, the binary hypercube and the mesh all belong to this new class of interconnections. In practical cases, HOWs have higher bisection width than tori with similar node and channel costs. Also, HOWs have a very large degree of fault tolerance. This paper focuses on 2-D HOW systems. We analyze the hardware cost of HOWs, present graph embeddings and communications algorithms for HOWs, carry out performance comparisons with binary hypercubes and GHs and simulate HOWs under heavy communication loads. Our results show the suitability of HOWs for very-high-performance computing.

This paper presents results of evaluating the communications capabilities of the generalized hypercube interconnection network. The generalized hypercube has outstanding topological properties, but it has not been implemented on a large scale because of its very high wiring complexity. For this reason, this network has not been studied extensively in the past. However, recent and expected technological advancements will soon render this network viable for massively parallel systems. We first present implementations of randomized many-to-all broadcasting and multicasting on generalized hypercubes, using as the basis the one-to-all broadcast algorithm presented by Fragopoulou et al. (1996). We test the proposed implementations under realistic communication traffic patterns and message generations, for the all-port model of communication. Our results show that the size of the intermediate message buffers has a significant effect on the total communication time, and this effect becomes very dramatic for large systems with large numbers of dimensions. We also propose a modification of this multicast algorithm that applies congestion control to improve its performance. The results illustrate a significant improvement in the total execution time and a reduction in the number of message contentions, and also prove that the generalized hypercube is a very versatile interconnection network. Copyright © 1999 John Wiley & Sons, Ltd.

In the paper we present an algorithm for creating region-adjacency-graph (RAG) pyramids on TurboNet, an experimental parallel computer system. Each level of these hierarchies of irregular tessellations is generated by independent stochastic processes that adapt the structure of the pyramid to the content of the image. RAGs can be used in multiresolution image analysis to extract connected components from labeled images. The implementation of the algorithm is discussed and performance results are presented for three different communication techniques which are supported by the TurboNet's hybrid architecture. The results indicate that efficient communications are vital to good performance of the algorithm. © 1997 by John Wiley & Sons, Ltd.

The paper presents several parallel DSP (digital signal processing) algorithms and their performance analysis, targetting a hybrid message-passing and shared-memory architecture that has been built at New Jersey Institute of Technology. The current version of our system contains eight powerful TMS320C40 processors. The algorithms are implemented on our system using message-passing only, shared-memory only, and, if possible, a combination of both of these parallel processing paradigms. Comparisons show that TurboNet's robust, hybrid architecture results in significant performance gains because of the flexibility it introduces.

The direct binary hypercube interconnection network has been very popular for the design of parallel computers, because it provides a low diameter and can emulate efficiently the majority of the topologies frequently employed in the development of algorithms. The last fifteen years have seen major efforts to develop image analysis algorithms for hypercube-based parallel computers. The results of these efforts have culminated in a large number of publications included in prestigious scholarly journals and conference proceedings. Nevertheless, the aforementioned powerful properties of the hypercube come at the cost of high VLSI complexity due to the increase in the number of communication ports and channels per PE (processing element) with an increase in the total number of PE’s. The high VLSI complexity of hypercube systems is undoubtedly their dominant drawback; it results in the construction of systems that contain either a large number of primitive PE’s or a small number of powerful PE’s. Therefore, low-dimensional k-ary n-cubes with lower VSLI complexity have recently drawn the attention of many designers of parallel computers. Alternative solutions reduce the hypercube’s VLSI complexity without jeopardizing its performance. Such an effort by Ziavras has resulted in the introduction of reduced hypercubes (RH’s). Taking advantage of existing high-performance routing techniques, such as wormhole routing, an RH is obtained by a uniform reduction in the number of edges for each hypercube node. An RH can also be viewed as several connected copies of the well-known cube-connected-cycles network. The objective here is to prove that parallel computers comprising RH interconnection networks are definitely good choices for all levels of image analysis. Since the exact requirements of high-level image analysis are difficult to identify, but it is believed that versatile interconnection networks, such as the hypercube, are suitable for relevant tasks, we investigate the problem of emulating hypercubes on RH’s. The ring (or linear array), the torus (or mesh), and the binary tree are the most frequently used topologies for the development of algorithms in low-level and intermediate-level image analysis. Thus, to prove the viability of the RH for the two lower levels of image analysis, we introduce techniques for embedding the aforementioned three topologies into RH’s. The results prove the suitability of RH’s for all levels of image analysis.

Abstract The problem or emulating multilevel structures on hypercube supercomputers is studied in the paper. The frequently used pyramid belongs to the class of multilevel structures. Several algorithms have been published in the literature for the emulation of pyramids by hypercubes. The paper extends the most important of these algorithms to make them applicable for multilevel structures. Results for the Connection Machine system CM‐2 with 16,384 processors are presented and comparative analysis of the new algorithms is carried out. It is shown that very often higher performance can be obtained for multilevel structures other than the pyramid.

The binary hypercube has been one of the most frequently chosen interconnection networks for parallel computers because it provides low diameter and is so robust that it can very efficiently emulate a wide variety of other frequently used networks. However, the major drawback of the hypercube is the increase in the number of communication channels for each processor with an increase in the total number of processors in the system. This drawback has a direct effect on the very large scale integration complexity of the hypercube network. This short note proposes a new topology that is produced from the hypercube by a uniform reduction in the number of edges for each node. This edge reduction technique produces networks with lower complexity than hypercubes while maintaining, to a high extent, the powerful hypercube properties. An extensive comparison of the proposed reduced hypercube (RH) topology with the conventional hypercube is included. It is also shown that several copies of the popular cube-connected cycles network can be emulated simultaneously by an RH with dilation 1.>

Abstract The paper presents a comparative analysis for algorithms that map pyramids onto hypercubes. The analysis is based on some important performance measures from graph theory and actual results from a Connection Machine system CM‐2 containing 16K processors. Connection Machine results are presented for pyramid algorithms that compute the perimeter of objects, apply 2‐dimensional convolution, and segment images.

Proposes techniques for mapping application algorithms onto a class of hierarchically structured parallel computing systems. Multiprocessors of this type are capable of efficiently solving a variety of scientific problems because they can efficiently implement both local and global operations for data in a two-dimensional array format. Among the set of candidate application domains, low-level and intermediate-level image processing and computer vision (IPCV) are characterized by high-performance requirements. Emphasis is given to IPCV algorithms. The importance of the mapping techniques stems from the fact that the current technology cannot be used to build cost-effective and efficient systems composed of very large numbers of processors, so the performance of various systems of lower cost should be investigated. Both analytical and simulation results prove the effectiveness and efficiency of the proposed mapping techniques.>

Modified hypercubes (MHs) have been proposed as the building blocks of hypercube-based parallel systems that support incremental growth techniques. In contrast, systems comprising the standard hypercube cannot be expanded in practice. Processor allocation for MHs is a more difficult task due to a slight deviation in their topology from that of the hypercube. The authors address the processor allocation problem for MHs and propose two strategies which are based, partially or entirely, on a table lookup approach. The proposed strategies are characterized by a perfect subcube recognition ability and a superior performance. Furthermore, two existing processor allocation strategies for pure hypercubes, namely the buddy and free list strategies, are shown to be ineffective for MHs, in the light of their inability to recognize many available subcubes.>

Hierarchically-structured arrays of processors have been widely used in the low-level and the intermediate-level phases of computer vision. This is because tasks in these phases require both local and global operations, when the two-dimensional array structure of the image is considered. This paper introduces mapping (process assignment) algorithms for systems in the above class. It is the first time in parallel computer vision that both the domain and the range of the mapping functions are in a general set of hierarchically-structured arrays of processors. More specifically, the systems being studied here are not necessarily homogeneous; the processing powers of processors at different levels and the reductions between different pairs of consecutive levels are allowed to vary. Efficient mapping is achieved by first proposing objective functions, so that each objective function measures the quality of a given mapping with respect to a particular optimization goal. Mapping algorithms, one for each objective function, that attempt to produce an optimal mapping by minimizing the corresponding objective function, are then proposed. It is proven theoretically that our mapping algorithms always yield an optimal solution for systems composed of processors with identical processing powers. In all other cases, some assignment choices in the algorithms allow to take advantage of the increased processing powers of processors.