High-precision virtual environments are increasingly important for various education, simulation, training, performance, and entertainment applications. We present HoloCamera, an innovative volumetric capture instrument to rapidly acquire, process, and create cinematic-quality virtual avatars and scenarios. The HoloCamera consists of a custom-designed free-standing structure with 300 high-resolution RGB cameras mounted with uniform spacing spanning the four sides and the ceiling of a room-sized studio. The light field acquired from these cameras is streamed through a distributed array of GPUs that interleave the processing and transmission of 4K resolution images. The distributed compute infrastructure that powers these RGB cameras consists of 50 Jetson AGX Xavier boards, with each processing unit dedicated to driving and processing imagery from six cameras. A high-speed Gigabit Ethernet network fabric seamlessly interconnects all computing boards. In this systems paper, we provide an in-depth description of the steps involved and lessons learned in constructing such a cutting-edge volumetric capture facility that can be generalized to other such facilities. We delve into the techniques employed to achieve precise frame synchronization and spatial calibration of cameras, careful determination of angled camera mounts, image processing from the camera sensors, and the need for a resilient and robust network infrastructure. To advance the field of volumetric capture, we are releasing a high-fidelity static light-field dataset, which will serve as a benchmark for further research and applications of cinematic-quality volumetric light fields.

Insights from functional Magnetic Resonance Imaging (fMRI), as well as recordings of large numbers of neurons, reveal that many cognitive, emotional, and motor functions depend on the multivariate interactions of brain signals. To decode brain dynamics, we propose an architecture based on recurrent neural networks to uncover distributed spatiotemporal signatures. We demonstrate the potential of the approach using human fMRI data during movie-watching data and a continuous experimental paradigm. The model was able to learn spatiotemporal patterns that supported 15-way movie-clip classification (∼90%) at the level of brain regions, and binary classification of experimental conditions (∼60%) at the level of voxels. The model was also able to learn individual differences in measures of fluid intelligence and verbal IQ at levels comparable to that of existing techniques. We propose a dimensionality reduction approach that uncovers low-dimensional trajectories and captures essential informational (i.e., classification related) properties of brain dynamics. Finally, saliency maps and lesion analysis were employed to characterize brain-region/voxel importance, and uncovered how dynamic but consistent changes in fMRI activation influenced decoding performance. When applied at the level of voxels, our framework implements a dynamic version of multivariate pattern analysis. Our approach provides a framework for visualizing, analyzing, and discovering dynamic spatially distributed brain representations during naturalistic conditions.

Light fields capture both the spatial and angular rays, thus enabling free-viewpoint rendering and custom selection of the focal plane. Scientists can interactively explore pre-recorded microscopic light fields of organs, microbes, and neurons using virtual reality headsets. However, rendering high-resolution light fields at interactive frame rates requires a very high rate of texture sampling, which is challenging as the resolutions of light fields and displays continue to increase. In this article, we present an efficient algorithm to visualize 4D light fields with 3D-kernel foveated rendering (3D-KFR). The 3D-KFR scheme coupled with eye-tracking has the potential to accelerate the rendering of 4D depth-cued light fields dramatically. We have developed a perceptual model for foveated light fields by extending the KFR for the rendering of 3D meshes. On datasets of high-resolution microscopic light fields, we observe 3.47×-7.28× speedup in light field rendering with minimal perceptual loss of detail. We envision that 3D-KFR will reconcile the mutually conflicting goals of visual fidelity and rendering speed for interactive visualization of light fields.

In graph coarsening, one aims to produce a coarse graph of reduced size while preserving important graph properties. However, as there is no consensus on which specific graph properties should be preserved by coarse graphs, measuring the differences between original and coarse graphs remains a key challenge. This work relies on spectral graph theory to justify a distance function constructed to measure the similarity between original and coarse graphs. We show that the proposed spectral distance captures the structural differences in the graph coarsening process. We also propose graph coarsening algorithms that aim to minimize the spectral distance. Experiments show that the proposed algorithms can outperform previous graph coarsening methods in graph classification and stochastic block recovery tasks.

Adversarial training has been successfully applied to build robust models at a certain cost. While the robustness of a model increases, the standard classification accuracy declines. This phenomenon is suggested to be an inherent trade-off. We propose a model that employs feature prioritization by a nonlinear attention module and L2 feature regularization to improve the adversarial robustness and the standard accuracy relative to adversarial training. The attention module encourages the model to rely heavily on robust features by assigning larger weights to them while suppressing non-robust features. The regularizer encourages the model to extract similar features for the natural and adversarial images, effectively ignoring the added perturbation. In addition to evaluating the robustness of our model, we provide justification for the attention module and propose a novel experimental strategy that quantitatively demonstrates that our model is almost ideally aligned with salient data characteristics. Additional experimental results illustrate the power of our model relative to the state of the art methods.

Diffusion Tensor Imaging (DTI) is an effective tool for the analysis of structural brain connectivity in normal development and in a broad range of brain disorders. However efforts to derive inherent characteristics of structural brain networks have been hampered by the very high dimensionality of the data, relatively small sample sizes, and the lack of widely acceptable connectivity-based regions of interests (ROIs). Typical approaches have focused either on regions defined by standard anatomical atlases that do not incorporate anatomical connectivity, or have been based on voxel-wise analysis, which results in loss of statistical power relative to structure-wise connectivity analysis. In this work, we propose a novel, computationally efficient iterative clustering method to generate connectivity-based whole-brain parcellations that converge to a stable parcellation in a few iterations. Our algorithm is based on a sparse representation of the whole brain connectivity matrix, which reduces the number of edges from around a half billion to a few million while incorporating the necessary spatial constraints. We show that the resulting regions in a sense capture the inherent connectivity information present in the data, and are stable with respect to initialization and the randomization scheme within the algorithm. These parcellations provide consistent structural regions across the subjects of population samples that are homogeneous with respect to anatomic connectivity. Our method also derives connectivity structures that can be used to distinguish between population samples with known different structural connectivity. In particular, new results in structural differences for different population samples such as Females vs Males, Normal Controls vs Schizophrenia, and different age groups in Normal Controls are also shown.

A highly multithreaded FFT-based direct Poisson solver that makes effective use of the capabilities of the current NVIDIA graphics processing units (GPUs) is presented. Our algorithms carefully manage the multiple layers of the memory hierarchy of the GPUs such that almost all the global memory accesses are coalesced into 128-byte device memory transactions, and all computations are carried out directly on the registers. A new strategy to interleave the FFT computation along each dimension with other computations is used to minimize the total number of accesses to the 3D grid. We illustrate the performance of our algorithms on the NVIDIA Tesla and Fermi architectures for a wide range of grid sizes, up to the largest size that can fit on the device memory ($(512\times 512\times 512)$ on the Tesla C1060/C2050 and $(512\times 256\times 256)$ on the GeForce GTX 280/480). We achieve up to 140 GFLOPS and a bandwidth of 70 GB/s on the Tesla C1060, and up to 375 GFLOPS with a bandwidth of 120GB/s on the GTX 480. The performance of our algorithms is superior to what can be achieved using the CUDA FFT library in combination with well-known parallel algorithms for solving tridiagonal linear systems of equations.

We develop an optimized FFT based Poisson solver on a CPU-GPU heterogeneous platform for the case when the input is too large to fit on the GPU global memory. The solver involves memory bound computations such as 3D FFT in which the large 3D data may have to be transferred over the PCIe bus several times during the computation. We develop a new strategy to decompose and allocate the computation between the GPU and the CPU such that the 3D data is transferred only once to the device memory, and the executions of the GPU kernels are almost completely overlapped with the PCI data transfer. We were able to achieve significantly better performance than what has been reported in previous related work, including over 50 GFLOPS for the three periodic boundary conditions, and over 40 GFLOPS for the two periodic, one Neumann boundary conditions. The PCIe bus bandwidth achieved is over 5GB/s, which is close to the best possible on our platform. For all the cases tested, the single 3D PCIe transfer time, which constitutes a lower bound on what is possible on our platform, takes almost 70% of the total execution time of the Poisson solver.

Current high-throughput algorithms for constructing inverted files all follow the MapReduce framework, which presents a high-level programming model that hides the complexities of parallel programming. In this paper, we take an alternative approach and develop a novel strategy that exploits the current and emerging architectures of multicore processors. Our algorithm is based on a high-throughput pipelined strategy that produces parallel parsed streams, which are immediately consumed at the same rate by parallel indexers. We have performed extensive tests of our algorithm on a cluster of 32 nodes, and were able to achieve a throughput close to the peak throughput of the I/O system: a throughput of 280 MB/s on a single node and a throughput that ranges between 5.15 GB/s (1 Gb/s Ethernet interconnect) and 6.12 GB/s (10 Gb/s InfiniBand interconnect) on a cluster with 32 nodes for processing the ClueWeb09 data set. Such a performance represents a substantial gain over the best known MapReduce algorithms even when comparing the single node performance of our algorithm to MapReduce algorithms running on large clusters. Our results shed a light on the extent of the performance cost that may be incurred by using the simpler, higher level MapReduce programming model for large scale applications.

Visual exploration of volumetric datasets to discover the embedded features and spatial structures is a challenging and tedious task. In this paper we present a semi-automatic approach to this problem that works by visually segmenting the intensity-gradient 2D histogram of a volumetric dataset into an exploration hierarchy. Our approach mimics user exploration behavior by analyzing the histogram with the normalized-cut multilevel segmentation technique. Unlike previous work in this area, our technique segments the histogram into a reasonable set of intuitive components that are mutually exclusive and collectively exhaustive. We use information-theoretic measures of the volumetric data segments to guide the exploration. This provides a data-driven coarse-to-fine hierarchy for a user to interactively navigate the volume in a meaningful manner.

Given a collection of documents residing on a disk, we develop a new strategy for processing these documents and building the inverted files extremely fast. Our approach is tailored for a heterogeneous platform consisting of a multicore CPU and a highly multithreaded GPU. Our algorithm is based on a number of novel techniques including: (i) a high-throughput pipelined strategy that produces parallel parsed streams that are consumed at the same rate by parallel indexers, (ii) a hybrid trie and B-tree dictionary data structure in which the trie is represented by a table for fast look-up and each B-tree node contains string caches, (iii) allocation of parsed streams with frequent terms to CPU threads and the rest to GPU threads so as to match the throughput of parsed streams, and (iv) optimized CUDA indexer implementation that ensures coalesced memory accesses and effective use of shared memory. We have performed extensive tests of our algorithm on a single node (two Intel Xeon X5560 Quad-core) with two NVIDIA Tesla C1060 attached to it, and were able to achieve a throughput of more than 262 MB/s on the ClueWeb09 dataset. Similar results were obtained for widely different datasets. The throughput of our algorithm is superior to the best known algorithms reported in the literature even when compared to those run on large clusters.

No abstract available.

We present a number of optimization techniques to compute prefix sums on linked lists and implement them on multithreaded GPUs using CUDA. Prefix computations on linked structures involve in general highly irregular fine grain memory accesses that are typical of many computations on linked lists, trees, and graphs. While the current generation of GPUs provides substantial computational power and extremely high bandwidth memory accesses, they may appear at first to be primarily geared toward streamed, highly data parallel computations. In this paper, we introduce an optimized multithreaded GPU algorithm for prefix computations through a randomization process that reduces the problem to a large number of fine-grain computations. We map these fine-grain computations onto multithreaded GPUs in such a way that the processing cost per element is shown to be close to the best possible. Our experimental results show scalability for list sizes ranging from 1M nodes to 256M nodes, and significantly improve on the recently published parallel implementations of list ranking, including implementations on the Cell Processor, the MTA-8, and the NVIDIA GeForce 200 series. They also compare favorably to the performance of the best known CUDA algorithm for the scan operation on the Tesla C1060.

Abstract We present a new multithreaded implementation for the computationally demanding direct volume rendering (DVR) of volumetric data sets on desktop multicore processors using ray casting. The new implementation achieves interactive rendering of very large volumes, even on high resolution screens. Our implementation is based on a new algorithm that combines an object‐order traversal of the volumetric data followed by a focused ray casting. Using a very compact data structure, our method starts with a quick association of data subcubes with fine‐grain screen tiles appearing along the viewing direction in front‐to‐back order. The next stage uses very limited ray casting on the generated sets of subcubes while skipping empty or transparent space and applying early ray termination in an effective way. Our multithreaded implementation makes use of new dynamic techniques to ensure effective memory management and load balancing. Our software enables a user to interactively explore large data sets through DVR while arbitrarily specifying a 2D transfer function. We test our system on a wide variety of well‐known volumetric data sets on a two‐processor Clovertown platform, each consisting of a Quad‐Core 1.86 GHz Intel Xeon Processor. Our experimental tests demonstrate DVR at interactive rates for the largest data sets that can fit in the main memory on our platform. These tests also indicate a high degree of scalability, excellent load balancing, and efficient memory management across the data sets used. Copyright © 2009 John Wiley & Sons, Ltd.

We present a new method for the interactive rendering of isosurfaces using ray casting on multicore processors. This method consists of a combination of an object-order traversal that coarsely identifies possible candidate three-dimensional (3D) data blocks for each small set of contiguous pixels and an isosurface ray casting strategy tailored for the resulting limited-size lists of candidate 3D data blocks. Our implementation scheme results in a compact indexing structure and makes careful use of multithreading and memory management environments commonly present in multicore processors. Although static screen partitioning is widely used in the literature, our scheme starts with an image partitioning for the initial stage and then performs dynamic allocation of groups of ray casting tasks among the different threads to ensure almost equal loads among the different cores while maintaining spatial locality. We also pay a particular attention to the overhead incurred by moving the data across the different levels of the memory hierarchy. We test our system on a two-processor Clovertown platform, each consisting of a Quad-Core 1.86-GHz Intel Xeon Processor and present detailed experimental results for a number of widely different benchmarks. We show that our system is efficient and scalable and achieves high cache performance and excellent load balancing, resulting in an overall performance that is superior to any of the previous algorithms. In fact, we achieve interactive isosurface rendering on a screen with 1.0242 resolution for all the data sets tested up to the maximum size that can fit in the main memory of our platform.

In this paper, we introduce a new efficient data layout scheme to efficiently handle out-of-core axis-aligned slicing queries of very large multidimensional volumetric data. Slicing is a very useful dimension reduction tool that removes or reduces occlusion problems in visualizing 3D/4D volumetric data sets and that enables fast visual exploration of such data sets. We show that the data layouts based on typical space-filling curves are not optimal for the out-of-core slicing queries and present a novel component-based data layout scheme for a specialized problem domain, in which it is only required to provide fast slicing at every k-th value, for any k > 1. Our component-based data layout scheme provides much faster processing time for any axis-aligned slicing direction at every k-th value, k > 1, requiring less cache memory size and without any replication of data. In addition, the data layout can be generalized to any high dimension.

We discuss a new efficient out-of-core multidimensional indexing structure, information-aware 2n-tree, for indexing very large multidimensional volumetric data. Building a series of (n-1)-Dimensional indexing structures on n-Dimensional data causes a scalability problem in the situation of continually growing resolution in every dimension. However, building a single n-Dimensional indexing structure can cause an indexing effectiveness problem compared to the former case. The information-aware 2n-tree is an effort to maximize the indexing structure efficiency by ensuring that the subdivision of space have as similar coherence as possible along each dimension. It is particularly useful when data distribution along each dimension constantly shows a different degree of coherence from each other dimension. Our preliminary results show that our new tree can achieve higher indexing structure efficiency than previous methods.

We propose a novel Persistent OcTree (POT) indexing structure for accelerating isosurface extraction and spatial filtering from volumetric data. This data structure efficiently handles a wide range of visualization problems such as the generation of view-dependent isosurfaces, ray tracing, and isocontour slicing for high dimensional data. POT can be viewed as a hybrid data structure between the interval tree and the Branch-On-Need Octree (BONO) in the sense that it achieves the asymptotic bound of the interval tree for identifying the active cells corresponding to an isosurface and is more efficient than BONO for handling spatial queries. We encode a compact octree for each isovalue. Each such octree contains only the corresponding active cells, in such a way that the combined structure has linear space. The inherent hierarchical structure associated with the active cells enables very fast filtering of the active cells based on spatial constraints. We demonstrate the effectiveness of our approach by performing view-dependent isosurfacing on a wide variety of volumetric data sets and 4D isocontour slicing on the time-varying Richtmyer-Meshkov instability dataset.

Emerging technologies in high speed NAS, hierarchical storage management systems, and networked systems that virtualize interconnected storage over IP and fiber-channel networks, promise to consolidate distributed data stores onto large-scale professionally managed enterprise storage environments. We describe the software architecture of the PAWN (producer-archive workflow network) environment that enables scalable, reliable marshalling and organization of distributed data into such enterprise storage environments. PAWN was initially developed to capture the core elements required for long term preservation of digital objects as identified by researchers in the digital library and archiving communities. In this paper, we show how PAWN can be extended to enable multiple clients at a number of distributed sites to prepare, organize, and bulk transfer large scale data onto clusters of servers that securely verify the integrity of the data, register the metadata, and store the data into an enterprise storage environment. PAWN allows detailed description, auditing, and organization of the data, and hence allows for efficient management, access, and disaster recovery. The basic software components are based on open standards and Web technologies, and hence are platform independent.

Preservation environments manage digital records for time periods that are much longer than that of a single vendor product. A primary requirement is the preservation of the authenticity and integrity of the digital records while simultaneously minimizing the cost of long-term storage, as the data is migrated onto successive generations of technology. The emergence of low-cost storage hardware has made it possible to implement innovative software systems that minimize risk of data loss and preserve authenticity and integrity. This paper describes software mechanisms in use in current persistent archives and presents an example based upon the NARA research prototype persistent archive.

Using the notions of Q-heaps and fusion trees developed by Fredman and Willard, we develop general transformation techniques to reduce a number of computational geometry problems to their special versions in partially ranked spaces. In particular, we develop a fast fractional cascading technique, which uses linear space and enables sublogarithmic iterative search on catalog trees in the case when the degree of each node is bounded by $O(\log^{\epsilon}n)$ for some constant $\epsilon >0$, where n is the total size of allthe lists stored in the tree. We apply the fast fractional cascading technique in combination with the other techniques to derive the first linear-space sublogarithmic time algorithms for two fundamental geometric retrieval problems: orthogonal segment intersection and rectangular point enclosure.

We consider the problem of organizing large scale earth science raster data to efficiently handle queries for identifying regions whose parameters fall within certain range values specified by the queries. This problem seems to be critical to enabling basic data mining tasks such as determining associations between physical phenomena and spatial factors, detecting changes and trends, and content based retrieval. We assume that the input is too large to fit in internal memory and hence focus on data structures and algorithms that minimize the I/O bounds. A new data structure, called a tree-of-regions (ToR), is introduced and involves a combination of an R-tree and efficient representation of regions. It is shown that such a data structure enables the handling of range queries in an optimal I/O time, under certain reasonable assumptions. We also show that updates to the ToR can be handled efficiently. Experimental results for a variety of multi-valued earth science data illustrate the fast execution times of a wide range of queries, as predicted by our theoretical analysis.

During the past few decades, we witnessed the emergence of a considerable number of parallel and distributed computation models, most of which survived for only a brief period of time. Moreover, the development of efficient and scalable parallel programs that are portable across different multiprocessor architectures remains to be a difficult task requiring a good understanding of several low-level details. The emergence of new paradigms such as optical computing, quantum computing, and DNA computing has again raised the issue of suitable parallel computation models, and which model is the right one for which paradigm. We will focus in this talk on the class of clusters of Symmetric Multiprocessors and give a brief overview of the related issues and the suitability of some of the proposed models. We will also report some of the experimental results for a number of applications.

Article Free Access Share on MOCHA: a database middleware system featuring automatic deployment of application-specific functionality Authors: Manuel Rodríguez-Martínez Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College ParkView Profile , Nick Roussopoulos Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College ParkView Profile , John M. McGann Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College ParkView Profile , Stephen Kelley Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College ParkView Profile , Vadim Katz Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College ParkView Profile , Zhexuan Song Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College ParkView Profile , Joseph JáJá Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College ParkView Profile Authors Info & Claims SIGMOD '00: Proceedings of the 2000 ACM SIGMOD international conference on Management of dataMay 2000 https://doi.org/10.1145/342009.336575Published:16 May 2000Publication History 5citation34DownloadsMetricsTotal Citations5Total Downloads34Last 12 Months11Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Summary form only given. The LZW algorithm is the most popular dictionary-based adaptive text compression scheme [Welch 1984]. In the LZW algorithm, a changing dictionary contains common strings that have been encountered so far in the text. The motivation for the present research is to explore an on-line variable-length binary encoding. We apply this encoding to LZW codes for remedy of the problem that we discussed in Acharya and Mukherjee [1995]. We call it the LZWAJ algorithm.

A fundamental challenge for parallel computing is to obtain high-level, architecture independent, algorithms which execute efficiently on general-purpose parallel machines.With ing problem posed by the NAS Integer Sorting ( 1S) Benchmark.

We introduce a computation model for developing and analyzing parallel algorithms on distributed memory machines. The model allows the design of algorithms using a single address space and does not assume any particular interconnection topology. We capture performance by incorporating a cost measure for interprocessor communication induced by remote memory accesses. The cost measure includes parameters reflecting memory latency, communication bandwidth, and spatial locality. Our model allows the initial placement of the input data and pipelined prefetching. We use our model to develop parallel algorithms for various data rearrangement problems, load balancing, sorting, FFT, and matrix multiplication. We show that most of these algorithms achieve optimal or near optimal communication complexity while simultaneously guaranteeing an optimal speed-up in computational complexity. Ongoing experimental work in testing and evaluating these algorithms has thus far shown very promising results.

This paper presents efficient and portable implementations of two useful primitives in image processing algorithms, histogramming and connected components. Our general framework is a single-address space, distributed memory programming model. We use efficient techniques for distributing and coalescing data as well as efficient combinations of task and data parallelism. Our connected components algorithm uses a novel approach for parallel merging which performs drastically limited updating during iterative steps, and concludes with a total consistency update at the final step. The algorithms have been coded in Split-C and run on a variety of platforms. Our experimental results are consistent with the theoretical analysis and provide the best known execution times for these two primitives, even when compared with machine-specific implementations. More efficient implementations of Split-C will likely result in even faster execution times.

Remotely sensed imagery has been used for developing and validating various studies regarding land cover dynamics. However, the large amounts of imagery collected by the satellites are largely contaminated by the effects of atmospheric particles. The objective of atmospheric correction is to retrieve the surface reflectance from remotely sensed imagery by removing the atmospheric effects. We introduce a number of computational techniques that lead to a substantial speedup of an atmospheric correction algorithm based on using look-up tables. Excluding I/O time, the previous known implementation processes one pixel at a time and requires about 2.63 seconds per pixel on a SPARC-10 machine, while our implementation is based on processing the whole image and takes about 4-20 microseconds per pixel on the same machine. We also develop a parallel version of our algorithm that is scalable in terms of both computation and I/O. Experimental results obtained show that a Thematic Mapper (TM) image (36 MB per band, 5 bands need to be corrected) can be handled in less than 4.3 minutes on a 32-node CM-5 machine, including I/O time.

Develops efficient algorithms for low and intermediate level image processing on the scan line array processor, a SIMD machine consisting of a linear array of cells that processes images in a scan line fashion. For low level processing, the authors present algorithms for block DFT, block DCT, convolution, template matching, shrinking, and expanding which run in real-time. By real-time, the authors mean that, if the required processing is based on neighborhoods of size m/spl times/m, then the output lines are generated at a rate of O(m) operations per line and a latency of O(m) scan lines, which is the best that can be achieved on this model. The authors also develop an algorithm for median filtering which runs in almost real-time at a cost of O(m log m) time per scan line and a latency of [m/2] scan lines. For intermediate level processing, the authors present optimal algorithms for translation, histogram computation, scaling, and rotation. The authors also develop efficient algorithms for labelling the connected components and determining the convex hulls of multiple figures which run in O(n log n) and O(n log/sup 2/n) time, respectively. The latter algorithms are significantly simpler and easier to implement than those already reported in the literature for linear arrays.>

This article introduces scalable data parallel algorithms for image processing. Focusing on Gibbs and Markov random field model representation for textures, we present parallel algorithms for texture synthesis, compression, and maximum likelihood parameter estimation, currently implemented on Thinking Machines CM-2 and CM-5. The use of fine-grained, data parallel processing techniques yields real-time algorithms for texture synthesis and compression that are substantially faster than the previously known sequential implementations. Although current implementations are on Connection Machines, the methodology presented enables machine-independent scalable algorithms for a number of problems in image processing and analysis.

A new parallel algorithm for the prefix minima problem is presented for inputs drawn from the range of integers $[1..s]$. For an input of size n, it runs in $O(\log \log \log s)$ time and $O(n)$ work (which is optimal). A faster algorithm is presented for the special case $s = n$; it runs in $O(\log ^ * n)$ time with optimal work. Both algorithms are for the Priority concurrent-read concurrent-write parallel random access machine (CROW PRAM). A possibly surprising outcome of this work is that, whenever the range of the input is restricted, the prefix minima problem can be solved significantly faster than the $\Omega (\log \log n)$ time lower bound in a decision model of parallel computation, as described by Valiant [SIAM J. Comput., 4 (1975), pp. 348–355]. The top-bottom routing problem, which is an important subproblem of routing wires around a rectangle in two layers, is also considered. It is established that, for parallel (and hence for serial) computation, the problem of top-bottom routing is no harder than the prefix minima problem with $s = n$, thus giving an $O(\log ^ * n)$ time optimal parallel algorithm for the top-bottom routing problem. This is one of the first nontrivial problems to be given an optimal parallel algorithm that runs in sublogarithmic time.

Abstract The synthetic‐perturbation screening (SPS) methodology is based on an empirical approach; SPS introduces artificial perturbations into the MIMD program and captures the effects of such perturbations by using the modern branch of statistics called design of experiments. SPS can provide the basis of a powerful tool for screening MIMD programs for performance bottlenecks. This technique is portable across machines and architectures, and scales extremely well on massively parallel processors. The purpose of this paper is to explain the general approach and to extend it to address specific features that are the main source of poor performance on the shared memory programming model. These include performance degradation due to load imbalance and insufficient parallelism, and overhead introduced by synchronizations and by accessing shared data structures. We illustrate the practicality of SPS by demonstrating its use on two very different case studies: a large image understanding benchmark and a parallel quicksort.

An optimal unified architecture that can efficiently compute the discrete cosine, sine, Hartley, Fourier, lapped orthogonal, and complex lapped transforms for a continuous stream of input data that arise in signal/image communications is proposed. This structure uses only half as many multipliers as the previous best known scheme (Liu and Chiu, 1993). The proposed architecture is regular, modular, and has only local interconnections in both data and control paths. There is no limitation on the transform size N and only 2N-2 multipliers are needed for the DCT. The throughput of this scheme is one input sample per clock cycle. The authors provide a theoretical justification by showing that any discrete transform whose basis functions satisfy the fundamental recurrence formula has a second-order autoregressive structure in its filter realization. They also demonstrate that dual generation transform pairs share the same autoregressive structure. They extend these time-recursive concepts to multi-dimensional transforms. The resulting d-dimensional structures are fully-pipelined and consist of only d 1D transform arrays and shift registers.>

We develop efficient algorithms for low and intermediate level image processing on the scan line array processor that handles images in a scan line fashion. For low level processing, we present algorithms for block DFT, block DCT, convolution, template matching, shrinking, and expanding. These algorithms run in real-time - that is, the output lines are generated at the rate of O(m) time per line, where the required processing is based on neighborhoods of size m x m. For intermediate level processing, we present efficient algorithms for scaling, translation, connected components, and convex hulls of multiple figures.

The Synthetic-Perturbation Tuning (SPT) methodology is base d on compirical approach that introduces artificial delays into the MIMD program and captures the effects of such delays by using the modrn branch statistics called design of experiments.

We describe an efficient parallel algorithm to solve the single function coarsest partition problem. The algorithm runs in O (log n) time using O(n log log n) operations on the arbitrary CRCW PRAM. The previous best-known algorithms run in O(log2 n) time using O(n log2n) operations on the CREW PRAM, and O(log n) time using O (n log n) operations on the arbitrary CRCW PRAM. Our solution is based on efficient algorithms for solving several subproblems that are of independent interest. In particular, we present efficient parallel algorithms to find a minimal starting point of a circular string with respect to lexicographic ordering and to sort lexicographically a list of strings of different lengths.

Parallel algorithms for several important combinatorial problems such as the all nearest smaller values problem, triangulating a monotone polygon, and line packing are presented. These algorithms achieve linear speedups on the pipelined hypercube, and provably optimal speedups on the shuffle-exchange and the cube-connected-cycles for any number p of processors satisfying 1>

The authors present a new systolic architecture for implementing finite state vector quantization in real-time for both speech and image data. This architecture is modular and has a very simple control flow. Only one processor is needed for speech compression. A linear array of processors is used for image compression; the number of processors needed is independent of the size of the image. Image data is processed at a rate of 1 pixel per clock cycle. An implementation at 31.5 MHz can quantize 1024*1024 pixel images at 30 frames/sec in real-time. The authors describe a VLSI implementation of these processors.>

The author presents parallel algorithms for several important combinatorial problems related to VLSI routing. These algorithms achieve linear speed-ups on the pipelined hypercube, and provably optimal speed-ups on the shuffle-exchange and the cube-connected-cycles, for any number p of processors satisfying 1>

The channel routing problem of a set of two-terminal nets in the knock-knee model is considered. A new approach to route all the nets within d tracks, where d is the density, such that the corresponding layout can be realized with three layers is developed. The routing and the layer assignment algorithms run in $O(\log n)$ time with $n / \log n$ processors on the CREW PRAM model under the reasonable assumption that all terminals lie in the range $[1,N]$, where $N = O(n)$.

The authors propose a family of VLSI architectures with area-time tradeoffs for computing (N*N* . . . *N) d-dimensional linear separable transforms. For fixed-precision arithmetic with b bits, the architectures have an area A=O(N/sup d+2a/) and computation time T=O(dN/sup d/2-a/b), and achieve the AT/sup 2/ bound of AT/sup 2/=O(n/sup 2/b/sup 2/) for constant d, where n=N/sup d/ and O>

It is established that several natural problems have triply logarithmic, or even faster, optimal parallel algorithms. These problems include: merging two sorted lists, where the values are drawn from a large, but restricted, domain on a CREW PRAM; finding all prefix minima, where the values are drawn from a restricted domain; and top-bottom global routing around a rectangle, a well-investigated problem in VLSI routing for which only highly involved serial algorithms were known.>

The channel-routing of a set of multiterminal nets in the standard two-layer model is considered. The sequential algorithms based on the greedy strategy do not seem to be easily parallelizable. Proposed is an efficient parallel algorithm for routing channels with cyclic constraints. The algorithm runs in time O(n/sup 2//p+log/sup 2/p), with p processors, on a shared memory parallel random access machine (PRAM) model where 1>

An efficient parallel algorithm to compute template matching of an N$0N input image with an M*M template on a single-instruction multiple-data (SIMD) mesh-connected computer with P processors is proposed. The input image is mapped into the processor array such that each processor stores N/sup 2//P data in the cyclic mode. The template values are circulated among the processors instead of being broadcast or stored in the processor memory. There is no movement of the intermediate results. The computation and the communication time complexity of the algorithm is O(M/sup 2/N/sup 2//P) for all P in the range M/sup 2/>

Two-dimensional systolic array implementations for computing the discrete Hartley transform (DHT) and the discrete cosine transform (DCT) when the transform size N is decomposable into mutually prime factors are proposed. The existing two-dimensional formulations for DHT and DCT are modified, and the corresponding algorithms are mapped into two-dimensional systolic arrays. The resulting architecture is fully pipelined with no control units. The hardware design is based on bit serial left to right MSB (most significant bit) to LSB (least significant bit) binary arithmetic.>

A hypercube algorithm to solve the list ranking problem is presented. Let n be the length of the list, and let p be the number of processors of the hypercube. The algorithm described runs in time O(n/p) when n= Omega (p/sup 1+ epsilon /) for any constant epsilon >0, and in time O(n log n/p+log/sup 3/ p) otherwise. This clearly attains a linear speedup when n= Omega (p/sup 1+ epsilon /). Efficient balancing and routing schemes had to be used to achieve the linear speedup. The authors use these techniques to obtain efficient hypercube algorithms for many basic graph problems such as tree expression evaluation, connected and biconnected components, ear decomposition, and st-numbering. These problems are also addressed in the restricted model of one-port communication.>

Consideration is given to the class of partially symmetric functions and a method for realizing them is outlined. Each such function can be expressed as a sum of totally symmetric functions such that a circuit can be designed with its complexity dependent on the size of such symmetric cover. The authors compare the sizes of symmetric and sum-of-product covers and show that the symmetric cover will be substantially smaller for this class of functions.>

Consideration is given to the problem of routing k two-terminal nets in the presence of obstacles in two models: the standard two-layer model and the knock-knee model. Determining routability is known to be NP-complete for arbitrary k. The authors introduce a technique that reduces the general problem into finding edge-disjoint paths in a graph whose size depends only on the size of the obstacles. Two optimization criteria are considered: the total length of the wires and the number of vias used.>

The direct sum conjecture states that the multiplicative complexity of disjoint sets of bilinear computations is the sum of their separate multiplicative complexities. This conjecture is known to hold for only a few specialized cases. In this paper, we establish its validity for large classes of computations. One such class can be defined as follows. Let $S_1 $ be a set of r$m \times n$ bilinear forms, and let $S_2 $ be a different set of s$p \times q$ bilinear forms. Then, if $2 \in \{ r,m,n,s,p,q\} $, we show that the direct sum conjecture holds over any field. The proof involves some nontrivial facts from linear algebra and relies on the theory of invariant polynomials. This result also settles the multiplicative complexity of pairs of bilinear forms over any field with large enough cardinality. It is also shown that the direct sum conjecture is true for the case when $r = mn - 2$.

Several questions related to the complexity of communication over channels with noise are addressed. We compare some of our results to wellknown results in information theory. In particular we compare the following two problems. Assuming that the communication channel between two processors P1 and P2 makes an error with probability ε≫0, the identification problem is to determine whether P1 and P2 have the same n-bit integer. The decoding problem is for P2 to determine the n-bit integer of P1. For the latter problem we show that given any arbitrarily large constant λ≫0, there exists an ε, 0≪ε≪1/2, for which no scheme requiring less than λn bits of communication can guarantee (for large n) any bound q≪1 on the error probability. On the other hand, given any arbitrarily small constant γ≫0 and any ε, 0≪ε≪1/2, the identification problem can be solved with (1+γ)n bits of (one-way) communication with an error probability bounded by c2-αn, where c and α are positive constants. These techniques are extended to other problems, and a one-bit output Boolean function is shown to exhibit a similar behavior to that of the decoding problem regardless of how the input bits are partitioned among the two processors.

This correspondence examines the problem of sorting on a network of processors, where each processor consists of a single storage register and a small control unit capable of comparing two numbers and has a single serial memory attached to it. We show how to sort optimally on one- or two-dimensional arrays of p processors in time θ(n + (n2/p2)) and θ((n/√p) + (n2/p2)), respectively. Because of the implementational advantages of serial memories, we feel that our architecture will be attractive for several applications.

General lower bound techniques are developed to determine the VLSI complexity of graph problems with some surprising results that show a striking difference between this class of problems and the other classes studied in the literature.The results show that the VLSI complexity of graph problems depends crucially on several parameters such as the I/O formats, the locaUons of the I/O ports, and the Umlng of the I/O bits Almost all of our lower bounds can be matched with existing upper bounds or bounds obtained by some minor modificatmns of existing algorithms Categories and SubJect Descriptors: B.7.1 [

Simple general lower bound techniques are developed for measuring the amount of interprocessor commumcatlon required in distributed computing.Optimal bounds are shown for many problems, such as integer multiplication, integer division, matrix squaring, matrix inversion, solving a linear system of equations, and computing square roots.Using these techniques, one can unify and strengthen the area-time trade-off results known in the literature.Many new trade-off results are also shown in several of the existing models Categories and SubJect Descriptors: B.7. l [

We study four kinds of protocols in distributed computing. Besides the case of deterministic protocols, we consider random, nondeterministic and probabilistic models. We show a strict containment relationship with exponential gaps. We also explore in some depth the relationship between one-way and two-way communications. It is shown, for example, that the complexity classes of random one-way protocols and of deterministic two-way protocols are incomparable: exponential gaps exist in either direction. On the other hand there is no difference between the complexity of one-way and two-way communications in the nondeterministic case.

We propose a new VLSI architecture which allows many problems to be solved quite efficiently on chips with very small processing areas. We consider in detail the sorting problem and show how it can be solved quickly and elegantly on our model. We show that sorting n numbers can be done on a chip with processing area A = o(n) with an almost optimal speedup in a network with mesh-connected interconnections. The control is shown to be simple and easily implementable in VLSI.

We consider the problem of computing the permanent of an mxn matrix, m≪n, over an arbitrary commutative ring. The permanent is a central problem in the computational complexity of enumeration problems and arises in several applications. We introduce the class of multilinear programs, where the monomials of the factors of any multiplication come from different sets of rows. All the known algorithms to compute the permanent satisfy this property. These programs can be represented by arithmetic circuits with unbounded fan in. We show the following: 1) Given any positive integer k, no constant depth multilinear program with ≪nk arithmetic operations can compute the permanent of an mxn matrix, where m = Ω(γ(n)logn) for any increasing function γ(n). 2) There exists a polynomial-size multilinear program of depth 4 which computes the permanent of an mxn matrix for m = 0(logn/loglogn). 3) Any arbitrary arithmetic circuit that computes the permanent of an mxn matrix with depth ≪3 must be of exponential size for any m nonconstant. Our proofs use, in a nontrivial way, probabilistic techniques to establish several combinatorial facts.

The time-space relationship of several algebraic problems Is studied, using and extending previous known techmques Several results relating the algebraic properties of a set of functions to the structure of the graph of any straight-line program that computes this set are shown.A surprising result is obtained, namely, that matrix inversion ~s harder than matrix mulUplication in the sense that the timespace product TS ~s of h~gher order for matrix mversmn.Other results are also shown.

We consider the problem of evaluating arithmetic expressions under a set of algebraic laws including the distributive law. An arithmetic expression can be represented by a dag and our problem is to find an equivalent dag with the fewest number of interior nodes. We attack the case when it is possible to eliminate common subexpressions and transform the dag into a tree; efficient algorithms to handle different cases of this problem are developed. These algorithms are based on the following strategy: we first transform the dag into a tree, assuming that such a transformation is possible, and we later check to see whether the tree and the given dag are indeed equivalent.

We present efficient $(O(\log ^2 n))$ parallel algorithms for two classical graph problems: planarity testing and finding triconnected components. The algorithms use only a polynomial number of processors. Previous algorithms used $\Omega (n)$ operations, regardless of the number of available processors.

We consider the problem of computing a set of algebraic functions that involve extracting roots of various degrees. We show that the complexity of computing a large class of algebraic functions is determined by the Galois group G of the extension generated by the functions. We relate the minimum cost to decomposing G into a sequence of normal subgroups such that each factor group is cyclic. We derive an exact answer for the case when the cost is logarithmic, while we provide upper and lower bounds for all the other cases. On the other hand, we develop a reasonably fast algorithm for the abelian case which has been already solved by Pippenger.

Graph augmentation problems on a weighted graph involve determining a minimum-cost set of edges to add to a graph to satisfy a specified property, such as biconnectivity, bridge-connectivity or strong connectivity. These augmentation problems are shown to be NP-complete in the restricted case of the graph being initially connected. Approximation algorithms with favorable time complexity are presented and shown to have constant worst-case performance ratios.

Algorithms for solving graph problems on an unbounded parallel model of computation are considered. Parallel algorithms of time complexity $O(\log ^2 n)$ are described for finding biconnected components, bridges, minimum spanning trees and fundamental cycles. In the algorithms for finding minimum spanning trees, bridges, and fundamental cycles, the number of processors used is small enough that the parallel algorithm is efficient in comparison with the best sequential algorithms for these problems. Several other algorithms are presented which are especially suitable for processing sparse graphs.

We study the time-space relationship of several algebraic problems such as matrix multiplication and matrix inversion. Several results relating the algebraic properties of a set of functions to the structure of the graph of any straight-line program, that computes this set, are shown. Some of our results are the following. Multiplying m × n by n × p matrices with space S requires at least time T ≥ Ω(mnp/S). Inverting an n × n matrix with space S requires at least time T ≥ Ω(n4/S).

The study of the complexity of algebraic problems depends heavdy on the straight-line model which allows no loops or branches Given an algebraic function, a stralght-hne program generates this function by performing elementary arRhmetic operations on combinations of parameters defining the function and constants drawn from a certain set.The corresponding complexRy will, in general, depend on the algebraic properties of the constant set.This relationship ts investigated more closely for the class of problems consisting of blltnear forms It is seen that the size of the constant set, as well as its algebraic properties, plays an equally crucml role m determining the complexity of a set of bdmear forms.Several examples are given where parameters related to both of these properties appear exphcRly in the complexity expressions One such example is a set of n x n bflmear forms whose complexity is n + [(n -l)/p], where p is the cardmahty of the field of constants and 1 is the number of distinct linear roots of a polynomial associated with the given set of bihnear forms The techmques used are fairly general and could be useful in several other problems.

We consider the general problem of computing sets of bilinear forms in commuting indeter-minates. We develop lower bound techniques which seem to be more powerful than those already known in the literature. We show that duality theory as it is known for bilinear forms with noncommuting indeter-minates does not hold in the commutative case; we prove that the multiplication of $2 \times n$ by $n \times 2$ matrices requires at least $\lceil 27n/8 \rceil $ multiplications while it is possible to multiply $2 \times 2$ by $2 \times n$ matrices using only $3n + 2$ multiplications. Moreover we settle the question of whether commutativity can reduce the number of multiplications by a factor of $\frac{1}{2}$, by showing that this can never happen. We also show that, over algebraically closed fields, the complexity of computing a pair of bilinear forms is the same whether or not commutativity is allowed.

We consider the problem of computing a set of bilinear forms in the case when the indeterminates commute. We develop lower bound techniques which seem to be more powerful than those already known in the literature for the commutative case. An unexpected result is the fact that Duality theory does not hold in the commutative case; we prove that the multiplication of 2 × n by n × 2 matrices requires at least [27n/8] multiplications while it is possible to multiply 2 × 2 by 2 × n matrices using only 3n + 2 multiplications. We also settle the question of whether commutativity can reduce the number of multiplications by 1/2 by showing that this can never happen.

A large class of multiplication problems in arithmetic complexity can be viewed as the simultaneous evaluation of a set of bilinear forms. This class includes the multiplication of matrices, polynomials, quaternions, Cayley and complex numbers. Considering bilinear algorithms, the optimal number of nonscalar multiplications can be described as the rank of a three-tensor or as the smallest member of rank one matrices necessary to include a given set of matrices in their span. In this paper, we attack a rather large subclass of three-tensors, namely that of $(p,q,2)$-tensors, for arbitrary p and q, and solve it completely in the case where the field of constants contains the roots of a polynomial associated with the given tensor. In all other cases, we prove that, in general, our bounds cannot be improved. The complexity of a general pair of bilinear forms is determined explicitly in terms of parameters related to Kronecker’s theory of pencils and to the theory of invariant polynomials. This reveals unexpected results and shows explicitly the dependence on the algebraic structure of the constants; we display, for example, a pair of $3 \times 3$ bilinear forms whose complexity is 3 over the field $Z_7 $ and which, however, requires exactly 4 nonscalar multiplications over the fields $Z_5 $ or $Z_{11} $. Corresponding optimal algorithms are described and several applications are considered.

A large class of multiplication problems in arithmetic complexity can be viewed as the simultaneous evaluation of a set of bilinear forms. This class includes the multiplication of matrices, polynomials, quaternions, Cayley and complex numbers. Considering bilinear algorithms, the optimal number of non-scalar multiplications can be described as the rank of a three-tensor or as the smallest number of rank one matrices necessary to include a given set of matrices in their span.