We introduce a novel, efficient computational method, ZEUS, for numerical optimization, and provide an open-source implementation. It has four key ingredients: (1) particle swarm optimization (PSO), (2) the use of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method, (3) automatic differentiation (AD), and (4) GPUs. Our approach addresses the computational challenges inherent in high-dimensional, non-convex optimization problems. In the first phase of the algorithm, we get a potentially good set of starting points using PSO. Thereafter, we run BFGS independently in parallel from these starting points. BFGS is one of the bestperforming algorithms for numerical optimization. However, it requires the gradient of the function being optimized. ZEUS integrates automatic differentiation into BFGS thus avoiding the need for the user to calculate derivatives explicitly. The use of GPUs allows ZEUS to speed up the calculations substantially. We carry out systematic studies to explore the trade-offs between the number of PSO iterations taken, starting points, and BFGS iteration depth. We show that a handful of iterations of PSO can improve global convergence when combined with BFGS. We also present performance studies using common test functions. The source code can be found at https://github.com/fnal-numerics/global-optimizer-gpu.

Many scientific and engineering applications require repeated calculations of derivatives of output functions with respect to input parameters. Automatic Differentiation (AD) is a method that automates derivative calculations and can significantly speed up code development. In Computational Fluid Dynamics (CFD), derivatives of flux functions with respect to state variables (Jacobian) are needed for efficient solutions of the nonlinear governing equations. AD of flux functions on graphics processing units (GPUs) is challenging as flux computations involve many intermediate variables that create high register pressure and require significant memory traffic because of the need to store the derivatives. This paper presents a forward-mode AD method based on multivariate dual numbers that addresses these challenges and simultaneously reduces the floating-point operation count. The dimension of the multivariate dual numbers is optimized for performance. The flux computations are restructured to minimize the number of temporary variables and reduce register pressure. For effective utilization of memory bandwidth, shared memory is used to store the local flux Jaco-bian. This AD implementation is compared with several other Jacobian implementations on an NVIDIA V100 GPU (V100). For three-dimensional perfect-gas compressible-flow equations implemented in a practical CFD code, the AD implementation of a flux Jacobian based on multivariate dual numbers of dimension 5 outperforms all other GPU AD implementations on V100. Its performance is comparable with the optimized hand-differentiated version. The implementation achieves 75% of the peak floating-point throughput and 61 % of the peak global device memory bandwidth usage.

Longitudinal data, which is widely used in many disciplines to study cause and effect, poses significant computational challenges to both modeling and analysis. Longitudinal data is composed of readings on the same variable collected over time and is often high-dimensional with correlated features. The combinatorial search approach for identifying the optimal features is unrealistic for most applications. The alternative approaches, such as heuristics, greedy searches, and regularization techniques, including LASSO, can result in models that suffer from both low accuracy and unclear feature attribution. In this paper, we propose a binary transformation on the data before applying LASSO for feature learning. As demonstrated in the paper, the binary transformation enhances signal in the data, resulting in highly accurate feature attribution, including associated time lags. It avoids the typical shortcomings of the LASSO algorithm, including saturation of the feature space and arbitrary or inconsistent sparse feature selection. Both synthetic data and real-world data sets were used to demonstrate the value of the proposed transformation and in all cases substantial improvements in feature learning were seen. In addition, the scalable parallelism of the solution is superior to that of the standard LASSO since transformation itself occurs in linear time and computing the LASSO solution using the transformed data results in a speedup of almost double.

We present a new adaptive parallel algorithm for the challenging problem of multi-dimensional numerical integration on massively parallel architectures. Adaptive algorithms have demonstrated the best performance, but efficient many-core utilization is difficult to achieve because the adaptive work-load can vary greatly across the integration space and is impossible to predict a priori. Existing parallel algorithms utilize sequential computations on independent processors, which results in bottlenecks due to the need for data redistribution and processor synchronization. Our algorithm employs a high-throughput approach in which all existing sub-regions are processed and sub-divided in parallel. Repeated sub-region classification and filtering improves upon a brute-force approach and allows the algorithm to make efficient use of computation and memory resources. A CUDA implementation shows orders of magnitude speedup over the fastest open-source CPU method and extends the achievable accuracy for difficult integrands. Our algorithm typically outperforms other existing deterministic parallel methods.

Genomic regions of high segmental duplication content and/or structural variation have led to gaps and misassemblies in the human reference sequence, and are refractory to assembly from whole-genome short-read datasets. Human subtelomere regions are highly enriched in both segmental duplication content and structural variations, and as a consequence are both impossible to assemble accurately and highly variable from individual to individual. Recently, we developed a pipeline for improved region-specific assembly called Regional Extension of Assemblies Using Linked-Reads (REXTAL). In this study, we evaluate REXTAL and genome-wide assembly (Supernova) approaches on 10X Genomics linked-reads data sets partitioned and barcoded using the Gel Bead in Emulsion (GEM) microfluidic method. Our results describe the accuracy and relative performance of these two approaches using the reference-based assessment module of QUAST. We show that REXTAL dramatically outperforms the Supernova whole genome assembler in subtelomeric segmental duplication regions, and results in highly accurate assemblies. Nearly all of the REXTAL "misassemblies" identified using default QUAST parameters simply pinpoint locations of tandem repeat arrays in the reference sequence where the repeat array length differs from that in the cognate REXTAL assembly by 1000 bp.

Cryptocurrencies are more than a decade old and several issues have been discovered since their then. One of these issues is a partial negation of the intent to “democratize” money by decentralizing control of the infrastructure that creates, transmits, and stores monetary data. The Programmatic Proof of Work (ProgPoW) algorithm is intended as a possible solution to this problem for the Ethereum cryptocurrency. This paper examines ProgPow’s claim to be Application Specific Integrated Circuit (ASIC) resistant. This is achieved by isolating the proof-of-work code from the Ethereum blockchain, inserting the ProgPoW algorithm, and measuring the performance of the new implementation as a multithread CPU program, as well as a GPU implementation. The most remarkable difference between the ProgPoW algorithm and the currently implemented Ethereum Proof-of Work is the addition of a random sequence of math operations in the main loop that require increased memory bandwidth. Analyzing and comparing the performance of the CPU and GPU implementations should provide an insight into how the ProgPoW algorithm might perform on an ASIC.

Particle colliders are essential tools in the pursuit of understanding matter interactions in the universe. The tremendous cost of their operation and requirement for finetuning, make high-fidelity particle collider simulations essential in ensuring optimal operation. Simulations of the beam-beam effects of colliding particle bunches are extremely time-consuming since they include hundreds of billions of particles that collide millions of times per second. A high degree of parallelization is required to decrease the execution time of such simulations. GPUs present an opportunity towards making such simulations viable, though several challenges must be overcome in order to achieve efficient parallelization. One major challenge addressed in this paper is an efficient simulation of multiple bunch collision on a cluster of GPUs. The numerous colliding bunches are subject to scheduling constraints, which requires the utilization of an efficient collision schedule algorithm, all the while ensuring that the processors are not underutilized and communication overheads are low. We implemented two schemes on a 8-node cluster with four K40 GPUs on each node for a total of 32 GPUs. We demonstrated an almost linear speedup for large bunches with the number of GPUs.

Parallel computing architectures like GPUs have traditionally been used to accelerate applications with dense and highly-structured workloads; however, many important applications in science and engineering are irregular and dynamic in nature, making their effective parallel implementation a daunting task. Numerical simulation of charged particle beam dynamics is one such application where the distribution of work and data in the accurate computation of collective effects at each time step is irregular and exhibits control-flow and memory access patterns that are not readily amenable to GPU's architecture. Algorithms with these properties tend to present both significant branch and memory divergence on GPUs which leads to severe performance bottlenecks.We present a novel cache-aware algorithm that uses machine learning to address this problem. The algorithm presented here uses supervised learning to adaptively model and track irregular access patterns in the computation of collective effects at each time step of the simulation to anticipate the future control-flow and data access patterns. Access pattern forecast are then used to formulate runtime decisions that minimize branch and memory divergence on GPUs, thereby improving the performance of collective effects computation at a future time step based on the observations from earlier time steps. Experimental results on NVIDIA Tesla K40 GPU shows that our approach is effective in maximizing data reuse, ensuring workload balance among parallel threads, and in minimizing both branch and memory divergence. Further, the parallel implementation delivers up to 485 Gflops of double precision performance, which translates to a speedup of up to 2.5X compared to the fastest known GPU implementation.

A key idea in de novo modeling of a medium-resolution density image obtained from cryo-electron microscopy is to compute the optimal mapping between the secondary structure traces observed in the density image and those predicted on the protein sequence. When secondary structures are not determined precisely, either from the image or from the amino acid sequence of the protein, the computational problem becomes more complex. We present an efficient method that addresses the secondary structure placement problem in presence of multiple secondary structure predictions and computes the optimal mapping. We tested the method using 12 simulated images from α-proteins and two Cryo-EM images of α-β proteins. We observed that the rank of the true topologies is consistently improved by using multiple secondary structure predictions instead of a single prediction. The results show that the algorithm is robust and works well even when errors/misses in the predicted secondary structures are present in the image or the sequence. The results also show that the algorithm is efficient and is able to handle proteins with as many as 33 helices.

Cryo-electron microscopy is a fast emerging biophysical technique for structural determination of large protein complexes. While more atomic structures are being determined using this technique, it is still challenging to derive atomic structures from density maps produced at medium resolution when no suitable templates are available. A critical step in structure determination is how a protein chain threads through the 3-dimensional density map. A dynamic programming method was previously developed to generate K best matches of secondary structures between the density map and its protein sequence using shortest paths in a related weighted graph. We discuss challenges associated with the creation of the weighted graph and explore heuristic methods to solve the problem of matching secondary structures.

Accurate simulation of collective effects in electron beams is one of the most challenging and computationally intractable problems in accelerator physics. More recently, researchers have developed a GPU-accelerated, high-fidelity simulation of electron beam dynamics that models the collective effects much more accurately. The simulation, however, is heavily data-intensive and memory-bound. In particular, data-dependent, irregular memory access patterns and control-flow in the collective effects computation phase of the simulation leads to a large number of non-coalesced memory accesses on the GPU. This significantly deteriorates the overall performance. Moreover, the parallel simulation exhibits poor data locality. This, together with non-coalesced memory accesses, leads to ineffective use of the memory hierarchy. We present a novel cache-aware algorithm that uses a locality heuristic to maximize data reuse by improving data locality. Additionally, the algorithm uses a control-flow heuristic to balance the workload among threads. The control-flow heuristic also minimizes threads divergence and enables reuse of partial results of previous iterations and thereby reducing the overall operation count. Experimental results on NVIDIA Tesla K40 GPU shows that our approach delivers up to 450 Gflops of double precision performance, which translates to a speedup of up to 16X compared with the current state-of-the-art GPU implementation.

Summary Financial markets change precipitously, and on‐demand pricing and risk models must be constantly recalibrated to reduce risk. However, certain classes of models are computationally intensive to robustly calibrate to intraday prices – stochastic volatility models being an archetypal example due to the non‐convexity of the objective function. In order to accelerate this procedure through parallel implementation, financial application developers are faced with an ever growing plethora of low‐level high‐performance computing frameworks such as Open Multi‐Processing, Open Computing Language, compute unified device architecture, or single instruction multiple data intrinsics, and forced to make a trade‐off between performance versus the portability, flexibility, and modularity of the code required to facilitate rapid in‐house model development and productionisation. This paper describes the acceleration of stochastic volatility model calibration on multi‐core CPUs and graphics processing units (GPUs) using the Xcelerit platform. By adopting a simple programming model, the Xcelerit platform enables the application developer to write sequential, high‐level C++ code, without concern for low‐level high‐performance computing frameworks. This platform provides the portability, flexibility, and modularity required by application developers. Speedups of up to 30x and 293x are respectively achieved on an Intel Xeon CPU and NVIDIA Tesla K40 GPU, compared with a sequential CPU implementation. The Xcelerit platform implementation is further shown to be equivalent in performance to a low‐level compute unified device architecture version. Overall, we are able to reduce the entire calibration process time of the sequential implementation from 6189 to 183.8 and 17.8 s on the CPU and GPU, respectively, without requiring the developer to reimplement in low‐level high‐performance computing frameworks. Copyright © 2015 John Wiley & Sons, Ltd.

MOTIVATION: Insertion sequences (ISs) are transposable elements present in most bacterial and archaeal genomes that play an important role in genomic evolution. The increasing availability of sequenced prokaryotic genomes offers the opportunity to study ISs comprehensively, but development of efficient and accurate tools is required for discovery and annotation. Additionally, prokaryotic genomes are frequently deposited as incomplete, or draft stage because of the substantial cost and effort required to finish genome assembly projects. Development of methods to identify IS directly from raw sequence reads or draft genomes are therefore desirable. Software tools such as Optimized Annotation System for Insertion Sequences and IScan currently identify IS elements in completely assembled and annotated genomes; however, to our knowledge no methods have been developed to identify ISs from raw fragment data or partially assembled genomes. We have developed novel methods to solve this computationally challenging problem, and implemented these methods in the software package ISQuest. This software identifies bacterial ISs and their sequence elements-inverted and direct repeats-in raw read data or contigs using flexible search parameters. ISQuest is capable of finding ISs in hundreds of partially assembled genomes within hours, making it a valuable high-throughput tool for a global search of IS elements. We tested ISQuest on simulated read libraries of 3810 complete bacterial genomes and plasmids in GenBank and were capable of detecting 82% of the ISs and transposases annotated in GenBank with 80% sequence identity. CONTACT: [email protected].

The k-core of a graph is the largest induced subgraph with minimum degree k. The k-core decomposition is to find the core number of each vertex in a graph, which is the largest value of k that the vertex belongs to a k-core. k-core decomposition has applications in many areas including network analysis, computational biology and graph visualization. The primary reason for it being widely used is the availability of an O(n + m) algorithm. The algorithm was proposed by Batagelj and Zaversnik and is considered the state-of-the-art algorithm for k-core decomposition. However, the algorithm is not suitable for parallelization and to the best of our knowledge there is no algorithm proposed for k-core decomposition on multicore processors. Also, the algorithm has not been experimentally analyzed for large graphs. Since the working set size of the algorithm is large, and the access pattern is highly random, it can be inefficient for large graphs. In this paper, we present an experimental analysis of the algorithm of Batagelj and Zaversnik and propose a new algorithm, ParK, that significantly reduces the working set size and minimizes the random accesses. We provide an experimental analysis of the algorithm using graphs with up to 65 million vertices and 1.8 billion edges. We compare the ParK algorithm with state-of-the-art algorithm and show that it is up to 6 times faster. We also provide a parallel methodology and show that the algorithm is amenable to parallelization on multicore architectures. We ran our experiments on a 4 socket Nehalem-EX processor which has 8 cores per socket and show that the algorithm scales up to 21 times using 32 cores.

Maximal clique enumeration (MCE) is a fundamental problem in graph theory. It plays a vital role in many network analysis applications and in computational biology. MCE is an extensively studied problem. Recently, Eppstein et al. proposed a state-of-the-art sequential algorithm that uses degeneracy based ordering of vertices to improve the efficiency. In this paper, we propose a new parallel implementation of the algorithm of Eppstein et al. using a new bit-based data structure. The new data structure not only reduces the working set size significantly but also by enabling the use of bit-parallelism improves the performance of the algorithm. We illustrate the significance of degeneracy ordering in load balancing and experimentally evaluate the impact of scheduling on the performance of the algorithm. We present experimental results on several types of synthetic and real-world graphs with up to 50 million vertices and 100 million edges. We show that our approach outperforms Eppstein et al.'s approach by up to 4 times and also scales up to 29 times when run on a multicore machine with 32 cores.

Electron cryomicroscopy is becoming a major experimental technique in solving the structures of large molecular assemblies. More and more three-dimensional images have been obtained at the medium resolutions between 5 and 10 Å. At this resolution range, major α-helices can be detected as cylindrical sticks and β-sheets can be detected as plain-like regions. A critical question in de novo modeling from cryo-EM images is to determine the match between the detected secondary structures from the image and those on the protein sequence. We formulate this matching problem into a constrained graph problem and present an O(Δ(2)N(2)2(N)) algorithm to this NP-Hard problem. The algorithm incorporates the dynamic programming approach into a constrained K-shortest path algorithm. Our method, DP-TOSS, has been tested using α-proteins with maximum 33 helices and α-β proteins up to five helices and 12 β-strands. The correct match was ranked within the top 35 for 19 of the 20 α-proteins and all nine α-β proteins tested. The results demonstrate that DP-TOSS improves accuracy, time and memory space in deriving the topologies of the secondary structure elements for proteins with a large number of secondary structures and a complex skeleton.

We present a memory-efficient algorithm and its implementation for solving multidimensional numerical integration on a cluster of compute nodes with multiple GPU devices per node. The effective use of shared memory is important for improving the performance on GPUs, because of the bandwidth limitation of the global memory. The best known sequential algorithm for multidimensional numerical integration CUHRE uses a large dynamic heap data structure which is accessed frequently. Devising a GPU algorithm that caches a part of this data structure in the shared memory so as to minimizes global memory access is a challenging task. The algorithm presented here addresses this problem. Furthermore we propose a technique to scale this algorithm to multiple GPU devices. The algorithm was implemented on a cluster of Intel®Xeon®CPU X5650 compute nodes with 4 Tesla M2090 GPU devices per node. We observed a speedup of up to 240 on a single GPU device as compared to a speedup of 70 when memory optimization was not used. On a cluster of 6 nodes (24 GPU devices) we were able to obtain a speedup of up to 3250. All speedups here are with reference to the sequential implementation running on the compute node.

Recent development in Graphics Processing Units (GPUs) has enabled a new possibility for highly efficient parallel computing in science and engineering. Their massively parallel architecture makes GPUs very effective for algorithms where processing of large blocks of data can be executed in parallel. Multidimensional integration has important applications in areas like computational physics, plasma physics, computational fluid dynamics, quantum chemistry, molecular dynamics and signal processing. The computationally intensive nature of multidimensional integration requires a high-performance implementation. In this study, we present an efficient deterministic parallel algorithm for adaptive multidimensional numerical integration on GPUs. Various optimization techniques are applied to maximize the utilization of the GPU. GPU-based implementation outperforms the best known sequential methods and achieves a speed-up of up to 100. It also shows good scalability with the increase in dimensionality.

SUMMARY In this paper, we present an efficient, easily parallelizable approach to solve planted motif problem (PMP). PMP is a well‐studied problem in computational biology. It is useful in developing methods for finding transcription factor binding sites, classifying sequences, and building phylogenetic trees. Many approaches to solve PMP can be found in the literature. But the problem with those approaches is that they are difficult to parallelize as they have been designed for serial computers. In this paper, we propose a simple, easily parallelizable enumeration‐based approach called BitBased. As with most other enumeration‐based approaches that have been proposed to solve PMP, BitBased is also limited by memory for solving large‐sized problems. To overcome this limitation, we propose various modifications, which not only reduce the memory requirement but also improve the performance of the approach. We have implemented our approach on multicore and GPU devices. We found that BitBased outperforms all the approaches proposed to solve PMP so far. BitBased is able to solve the (21,8) instance, which was not previously reported as solved in the literature. Copyright © 2012 John Wiley & Sons, Ltd.

The determination of the secondary structure topology is a critical step in deriving the atomic structure from the protein density map obtained from electron cryo-microscopy technique. This step often relies on the matching of two sources of information. One source comes from the secondary structures detected from the protein density map at the medium resolution, such as 5-10 A. The other source comes from the predicted secondary structures from the amino acid sequence. Due to the uncertainty in either source of information, a pool of possible secondary structure positions has to be sampled in order to include the true answer. A naive way to find the native topology is to exhaustively map the pool of possible secondary structures detected in the density map with the pool of the secondary structures predicted from the sequence and search for the topology with the lowest cost. This paper studies the question that is how to reduce the computation of the mapping when the uncertainty of the secondary structure predictions is considered. We present a method that combines the concept of dynamic graph with our previous work of using constrained shortest path to identify the topology of the secondary structures. We show a reduction of about 34.55% time as comparison to the naive way of handling the inaccuracies. To our knowledge, this is the Is computationally effective exact algorithm to identify the optimal topology of the secondary structures when the inaccuracy of the predicted data is considered.

Today computers have several levels of memory hierarchy. To obtain good performance on these processors it is necessary to design algorithms that minimize I/O traffic to slower memories in the hierarchy. In this article, we study the computation of option pricing using the binomial and trinomial models on processors with a multilevel memory hierarchy. We derive lower bounds on memory traffic between different levels of the hierarchy for these two models. We also develop algorithms for the binomial and trinomial models that have near-optimal memory traffic between levels. We have implemented these algorithms on an UltraSparc IIIi processor with a 4-level of memory hierarchy and demonstrated that our algorithms outperform algorithms without cache blocking by a factor of up to 5 and operate at 70% of peak performance.

One of the government missions identified by the federal enterprise architecture is to use computer and networking technologies to develop infrastructure to support information sharing within government organizations as well as with external stakeholders. Currently, considerable information is being maintained at individual organizations in the form of large repositories/digital libraries with no efficient means of sharing it with other government organizations and with other external user communities, including the general public. A major obstacle to information sharing is the lack of a framework and an infrastructure that allows government organizations to share information selectively with different user groups. Lack of such a framework creates unwillingness among government organizations to share their digital content. A mechanism needs to be in place where policy makers can specify which documents can be moved from one organization to another organization and/or who can access these transferred documents. Furthermore, a system is needed that enforces these policies in realtime when external events dictate a change of policies. In this paper, we propose a framework for specification, management and enforcement of dynamic access policies across multiple geographically distributed organizations. The framework can be instantiated to integrate with individual digital library systems and provide the necessary infrastructure to provide policy controlled access control management

In this paper, we propose a P2P digital library that takes advantage of P2P networks and digital libraries. The key problem with P2P network searches is the low recall value, time to completion and its high use of network bandwidth. In this paper we introduce Freelib a universal client that once installed on a user's machine will connect itself to a P2P network and after a few searches will become aware of the community the user belongs to. The architecture of Freelib is such that a Web of connections is created automatically for people who share common interests, i.e., have similar searches. We report in this paper on the first prototype client the design changes made in the architecture as we actually built the client and the development of an emulator that can validate the working of the client in a real P2P network.

The advancements in the Internet and Web technologies have fueled a growing interest in developing a Web-based distributed computing environment. We have designed and developed Arcade, a Web-based environment for designing, executing, monitoring and controlling distributed heterogeneous applications, which is easy to use and access, portable, and provides support through all phases of the application development and execution. A major focus of the environment is the specification of heterogeneous multidisciplinary applications. We focus on the visual and script-based specification interface of Arcade. The Web/browser-based visual interface is designed to be intuitive to use and can also be used for visual monitoring during execution. The script specification is based on XML to: make it portable across different frameworks; and make the development of our tools easier by using the existing freely available XML parsers and editors. There is a one-to-one correspondence between the visual and script-based interfaces allowing users to go back and forth between the two. To support this we have developed translators that translate a script-based specification to a visual-based specification and vice-versa. These translators are integrated with our tools and are transparent to users.

Parallel and distributed computing on a cluster of workstations is being increasingly applied to a variety of large size computational problems. Several software systems have been developed that make distributed computing available to an application programmer. However, these systems either are not Web-based or lack a collaborative environment. The increasing use of Web technology for Internet and Intranet applications is making the Web an attractive framework for solving distributed applications, in particular, because the interface can be made platform-independent. In this paper we describe JAVADC, a Web–Java-based framework for the execution of parallel SPMD applications which use PVM, pPVM and MPI. We also discuss the design of a collaborative, distributed computing environment, Arcade, focused on more general programming paradigms for multidisciplinary applications. Arcade is a Web-based integrated environment which provides support in all phases of the development of general multidisciplinary applications including the design, execution, monitoring and control of such applications. © 1997 John Wiley & Sons, Ltd.

The MPEG/audio is a standard for both transmitting and recording compressed audio. The MPEG algorithm achieves compression by exploiting the perceptual limitation of the human ear. The standard defines the decoding process and also the syntax of the coded bitstream. However, there is room for having different implementation to generate the compressed bitstream. We propose a high performance software implementation of the MPEG/audio encoder. We obtained more than a factor of five improvement over a straightforward implementation, on the IBM PowerPC, Model 250.

We propose two high performance algorithms for motion estimation searching. The first algorithm express minimum mean square error motion estimation in terms of a cross-correlation computation; this approach reduces the number of multiply-adds needed by almost factor of two, with further improvement possible when fast cross-correlation algorithms are used. In the second algorithm we express the motion estimation computation in a form similar to the matrix-matrix multiplication computation. We propose an efficient algorithm for this computation. The algorithm exploits the memory hierarchy of the target processor and gives optimal performance for this formulation. In certain cases, both approaches can be used simultaneously.

Execution time of an application running on a cluster of workstations is critically dependent upon the performance of the underlying communication network, especially when the application demands for large data transfers among workstations. In this research, we use parallel network approach to improve the communication network performance and demonstrate this in a real cluster computing environment using multiple Ethernets. We modified the PVM environment to pPVM to schedule the application data onto multiple networks, the scheduling strategy being either round-robin or adaptive. The adaptive strategy performs well for both equal and unequal distribution of background load on the channels, and also for time-varying background load.

Proposes a parallel high-performance fast Fourier transform (FFT) algorithm based on a multi-dimensional formulation. We use this to solve a commonly encountered FFT based kernel on a distributed memory parallel machine, the IBM scalable parallel system, SP1. The kernel requires a forward FFT computation of an input sequence, multiplication of the transformed data by a coefficient array, and finally an inverse FFT computation of the resultant data. We show that the multi-dimensional formulation helps in reducing the communication costs and also improves the single node performance by effectively utilizing the memory system of the node. We implemented this kernel on the IBM SP1 and observed a performance of 1.25 GFLOPS on a 64-node machine.>

The authors propose a feature-extraction-based algorithm (FEBA) for sparse matrix-vector multiplication. The key idea of FEBA is to exploit any regular structure present in the sparse matrix by extracting it and processing it separately. The order in which these structures are extracted is determined by the relative efficiency with which they can be processed. The authors have tested FEBA on IBM 3000 VF for matrices from the Harwell Boeing and OSL collection. The results obtained were on average five times faster than the ESSL routine which is based on the ITPACK storage structure.>

Systolic implementation of neural networks is suggested. These arrays do not suffer from long feedback connections. Various learning rules are incorporated in the suggested systolic implementation of neural networks. It is shown that these arrays can be easily generalized for multilayered feedforward networks.>