bluuebunny/crossref_metadata_2025 huggingface dataset:
Polarized distribution of ion channels within microdomains of the axon initial segment
Authors: Van Wart Audra , Trimmer James S. , Matthews Gary
Published: November 2006

Voltage‐gated sodium (Nav) channels accumulate at the axon initial segment (IS), where their high density supports spike initiation. Maintenance of this high density of Nav channels involves a macromolecular complex that includes the cytoskeletal linker protein ankyrin‐G, the only protein known to bind Nav channels and localize them at the IS. We found previously that Nav1.6 is the predominant Nav channel isoform at IS of adult rodent retinal ganglion cells. However, here we report that Nav1.6 immunostaining is consistently reduced or absent in short regions of the IS proximal to the soma, although both ankyrin‐G and pan‐Nav antibodies stain this region. We show that this proximal IS subregion is a unique axonal microdomain, containing an accumulation of Nav1.1 channels that are spatially segregated from the Nav1.6 channels of the distal IS. Additionally, we find that axonal Kv1.2 potassium channels are present within the distal IS, but are also excluded from the Nav1.1‐enriched proximal IS microdomain. Because ankyrin‐G was prominent in both proximal and distal subcompartments of the IS, where it colocalized with either Nav1.1 or Nav1.6, respectively, mechanisms other than association with ankyrin‐G must mediate differential targeting of Nav channel subtypes to achieve the spatial precision observed within the IS. This precise arrangement of ion channels within the axon initial segment is likely an important determinant of the firing properties of ganglion cells and other mammalian neurons. J. Comp. Neurol. 500:339–352, 2007. © 2006 Wiley‐Liss, Inc.
Vibration analysis of conical panels using the method of discrete singular convolution
Authors: Civalek Ömer
Published: November 2006

A discrete singular convolution (DSC) free vibration analysis of conical panels is presented. Regularized Shannon's delta kernel (RSK) is selected as singular convolution to illustrate the present algorithm. In the proposed approach, the derivatives in both the governing equations and the boundary conditions are discretized by the method of DSC. Effects of boundary conditions, vertex and subtended angle on the frequencies of conical panel are investigated. The effect of the circumferential node number on the vibrational behaviour of the panel is also analysed. The obtained results are compared with those of other numerical methods. Numerical results indicate that the DSC is a simple and reliable method for vibration analysis of conical panels. Copyright © 2006 John Wiley & Sons, Ltd.
Parallel computing comes of age: Supercomputer level parallel computations at Caltech
Authors: Fox Geoffrey C.
Published: November 2006

Parallel supercomputers are now in regular use at Caltech for several major scientific calculations. We use this experience to abstract a set of lessons for applications, decomposition, performance, hardware and software. We consider hypercubes, transputer arrays and the SIMD Connection Machine CM‐2 and AMT DAP. These are contrasted, where possible, with CRAY and other high performance conventional computers. Applications covered are lattice gauge theory, plasma physics, statistical and condensed matter physics, astronomical data analysis, quantum chemistry, graphics ray tracing, string dynamics, grain dynamics, astrophysical particle dynamics, computer chess and Kalman filters.
Experiments with multicomputer LU‐decomposition
Authors: van de Velde Eric F.
Published: November 2006

We present a new concurrent LU‐decomposition algorithm based on implicit pivoting of both rows and columns. This algorithm is, to a large extent, independent of the distribution of the matrix over the concurrent processes. As a result, it can be used in programs with dynamically varying data distributions. Another advantage is that most pivoting strategies are easily incorporated. We also introduce two new, intrinsically concurrent, pivoting strategies: multirow and multicolumn pivoting.

With this program, we study the performance of concurrent LU‐decomposition as a function of data distribution and pivoting strategy. We show that LU‐decomposition with some pivoting strategies is both faster and numerically more stable than LU‐decomposition without pivoting. Experimental evidence on the Symult 2010 and the iPSC/2 shows that, for performance considerations, pivoting is equivalent to randomizing the data distribution.
The schedule parallel programming package with recycling job queues and iterated dependency graphs
Authors: Hanson F. B. , Sorensen D. C.
Published: November 2006

The SCHEDULE parallel programming package has been modified so that many more total processes may be spawned as long as the number of currently active processes satisfy the former limits of the package rather than the cumulative total number. This has been accomplished principally by changing the queueing system for both the job parameter queue and the ready jobs queue. The original linear queues are converted to circular queues, in that finished places in the queues are reused for new jobs and that the physical end of the queue is logically connected to the physical beginning of the queue. Two additional features facilitate the change in queues. The first is the implementation of a third queue, a free list, which keeps a list of the currently free slots on the job parameter queue. The second new feature is the use of SCHEDULE generated job tags rather than user‐generated job tags within the package. The user program now gets a job tag number from SCHEDULE with a subroutine call. Another improvement permits the iteration of dependency graphs, with minimal restoration of dependency data. This improvement facilitates the application of the SCHEDULE package to iterations and time‐stepping problems, by saving and reusing the iterated part of the dependency graph. This feature can result in a significant reduction in the number of newly spawned processes that would otherwise be needed for iterations.
Construction of a large‐scale neural network: Simulation of handwritten Japanese character recognition on NCUBE
Authors: Joe Kazuki , Mori Yoshihiro , Miyake Sei
Published: November 2006

This paper describes how new learning methods may make it possible for a large‐scale, hierarchical neural network to recognize most Japanese handwritten characters. This is a very large and complex task, as the Japanese character set consists of about 3000 categories which can be written in many different ways. Such a difficult task can lead a neural network to converge very slowly and to yield recognition rates that are uneven between categories. To address these problems we here propose five learning methods as modifications of the conventional back‐propagation learning rule. These methods produce fast convergence, even recognition rates over all categories, and adequate recognition of test samples. We also describe how a large‐scale neural network can be built by dividing the recognition task into several subtasks, with networks for each subtask, and then integrating these subnetworks in a large network with a hierarchical structure. In a hierarchical network, the upper level network directly integrates outputs from each lower level network. Application of that network to handwritten Japanese character recognition has resulted in poor recognition, because lower level networks do not know about unknown input patterns, and the direct integration of ambiguous outputs from many lower level networks confuses the upper level network. We propose a new integration method which provides each subnetwork with more information as to how close an input pattern is to the categories of that subnetwork. This method resulted in high recognition performance for character recognition. We here described the above methods, and report the performance of our implementation of a neural network for the recognition of 71 Hiragana characters, and describe our implementation of this network on a hypercube concurrent computer.
A real‐time distributed algorithm for an aircraft longitudinal optimal autopilot
Authors: Tahir Jamel M. , Virk Gurvinder S.
Published: November 2006

This paper is concerned with fast and efficient computations for the solution of the two‐point boundary‐value problem that arises in optimal control of an aircraft longitudinal mode. The solution proposed is implemented on a T800 transputer network using parallel C and is shown to be adequate for real‐time control purposes.
Updating distributed variables in local computations
Authors: Gerndt Michael
Published: November 2006

This paper describes special aspects of MIMD parallelization in SUPERB. SUPERB is an interactive SIMD/MIMD parallelizing system for the SUPRENUM machine. The main topic of this paper is the updating of distributed variables in parallelized applications. The intended applications perform local computations on a large data domain.
Sorting with near linear speed‐up on tightly coupled multiprocessors
Authors: Wheat Mitchell
Published: November 2006

A new parallel sorting algorithm, called parsort, suitable for implementation on tightly coupled multiprocessors is presented. The algorithm is based upon quicksort and two‐way merging. An asynchronous parallel partitioning algorithm is used to distribute work evenly during merging to ensure a good load balance amongst processors, which is crucial if we are to achieve high efficiency. The implementation of this parallel sorting algorithm exhibits theoretical and measured near linear speed‐up when compared to sequential quicksort. This is illustrated by the results of experiments carried out on the Sequent Balance 8000 multiprocessor.
Real‐time multi‐scale vision on multi‐computers
Authors: Battiti Roberto
Published: November 2006

This paper investigates the use of large grain size multi‐computers for solving low‐ and intermediate‐level computer vision problems. The realization of a general multi‐resolution framework requiring a two‐dimensional grid of communicating processors is analysed, and the resulting speed‐up and total solution time as a function of software and hardware parameters is presented. The scheme is then specialized for two significant problems: surface reconstruction and optical flow. While the first can be solved with the standard full multigrid approach, the second requires an adaptive grid determined by a local decision: the appropriate resolution for different parts of the image is tuned in order to minimize the error in the coefficients of the differential equations.
Sequence comparison on the connection machine
Authors: Atallah Mikhail J. , McFaddin Scott
Published: November 2006

We give two parallel algorithms for sequence comparison on the Connection Machine 2 (CM‐2). The specific comparison measure we compute is theedit distance: given a finite alphabet ∑ and two input sequencesXϵ ∑+andYϵ ∑+the edit distanced(X,Y)is the minimum cost of transformingXintoYvia a series of weighted insertions, deletions and substitutions of characters. The edit distance comparison measure is equivalent to or subsumes a broad range of well known sequence comparison measures.

The CM‐2 is very fast at performing parallel prefix operations. Our contribution consists of casting the problem in terms of these operations. Our first algorithm computesd(X,Y)usingNprocessors andO(M S)time units, whereM= min(|X|,||Y|) + 1,N= max(|X|,|Y|) + 1 andSis the time required for a parallel prefix operation. The second algorithm computesd(X,Y)usingNMprocessors andO((logNlogM)(S+R)) time units, whereRis the time for a ‘router’ communication step—one in which each processor is able to read data, in parallel, from the memory of any other processor. Our algorithms can also be applied to several variants of the problem, such as subsequence comparisons, and one—many and many‐many comparisons on 'sequence databases'.
Tiny: An efficient routing harness for the Inmos transputer
Authors: Clarke Lyndon , Wilson Greg
Published: November 2006

Message‐based MIMD computers that support arbitrary connections over a small number of communications links cannot support parallel applications with complex communication patterns unless the support software includes message routing. This paper describes design issues for such software, using a router for the Inmos T800 transputer called Tiny as an example. Performance figures show that Tiny achieves near optimal routing performance given the hardware limits. Modifications to Tiny to monitor message traffic are also described.
Two approaches to the concurrent implementation of the prime factor algorithm on a hypercube
Authors: Aloisio G. , Lopinto E. , Veneziani N. , Fox G. C. , Kim J. S.
Published: November 2006

On sequential computers, the prime factor algorithm (PFA) allows the Computation of the discrete Fourier transform (DFT) with a higher efficiency than the traditional Cooley‐Tukey FFT algorithm (CTA). However, the PFA requires substantial data movement, which poses a challenging problem for distributed‐memory multi‐processor systems. In this paper, two approaches for a concurrent implementation of the PFA on these structures are presented. In the first approach, the concurrent PFA runs on all nodes of the multi‐processor system, which is inefficient on large configurations due to the large communication overhead. A second approach developed to reduce this bottleneck is also presented. These solutions have been benchmarked on Caltech hypercubes, and the performances achieved are reported. In both approaches, thecrystal_routeralgorithm was exploited as a concurrent technique for communicating data among nodes.
Global adaptive quadrature for the approximate computation of multidimensional integrals on a distributed‐memory multiprocessor
Authors: Lapegna Marco
Published: November 2006

In this paper we discuss the problem of computing a multidimensional integral on a MIMD distributed‐memory multiprocessor.

Adaptive quadrature is known as a good approach to the problem of achieving accuracy and reliability while attempting to minimize the number of function evaluations. The implementation makes use of dynamical data structures able to manage subinterval partition. On a distributed‐memory multiprocessor, each processor is able to execute code and to manipulate data structures in its own local memory only, and data are sent from one processor to another one by explicit message‐passing. Efficient implementation of an adaptive algorithm for the multidimensional quadrature on a parallel computer is quite difficult, because of the need for continuous information exchange between processors.

Our algorithm is based on a global adaptive strategy which dynamically balances the workload and reduces the data communication between processors in order to use the message‐passing environment efficiently.

The results and timings for several tests are given.
Sparse iterative algorithm software for large‐scale MIMD machines: An initial discussion and implementation
Authors: Shadid John N. , Tuminaro Ray S.
Published: November 2006

The parallelization of sophisticated applications has dramatically increased in recent years. As machine capabilities rise, greater emphasis on modeling complex phenomena can be expected. Many of these applications require the solution of large sparse matrix equations which approximate systems of partial differential equations (PDEs). Therefore we consider parallel iterative solvers for large sparse non‐symmetric systems and issues related to parallel sparse matrix software. We describe a collection of parallel iterative solvers which use a distributed sparse matrix format that facilitates the interface between specific applications and a variety of Krylov subspace techniques and multigrid methods. These methods have been used to solve a number of linear and non‐linear PDE problems on a 1024‐processor NCUBE 2 hypercube. Over 1 Gflop sustained computation rates are achieved with many of these solvers, demonstrating that high performance can be attained even when using sparse matrix data structures.
Voxel databases: A paradigm for parallelism with spatial structure
Authors: Williams Roy D.
Published: November 2006

This paper concerns parallel, local computations with a data structure such as a graph or mesh, which may be structured or unstructured. The target machine is a distributed‐memory parallel processor with vector or pipeline hardware on the processors, but software based on voxel databases also runs efficiently on shared‐memory and uniprocessor machines with and without vector hardware.

A voxel database (VDB) is a distributed shared memory where entities which share memory are those at the same geometric position. A VDB may be thought of as a dictionary of position‐subscript pairs, so that data may be associated with points in space by using the subscript of that point as an index into data arrays. The use of subscripts allows ease of programming and vectorization. The shared memory at each point is weakly coherent and may be either single‐writer, multiple‐reader—also known as the ghost node method—or multiple‐combiner, multiple‐reader memory. The VDB may be sorted to put special points at the beginning or end of the subscript list, and also to reduce cache‐miss inefficiencies. Support is also provided for arbitrary distribution of data entities between processors for load‐balancing.

The idea of VDBs and the corresponding software tool provide a clear and efficient way to program a large variety of mesh computations in Fortran or C, such that the execution of the program is independent of the distribution of data to processors, and the mesh may be topologically adapted and load‐balanced.

As an example we discuss the implementation of an unstructured finite‐element elliptic solver using a conjugate gradient method. We also discuss the implementations of a finite‐volume flux‐split fluid solver and of local adaptive refinement for meshes of simplices such as triangles or tetrahedra.
Parallel rendering of volumetric data set on distributed‐memory architectures
Authors: Montani C. , Perego R. , Scopigno R.
Published: November 2006

A solution is proposed to the problem of interactive visualization and rendering of volume data. Designed for parallel distributed memory MIMD architectures, the volume rendering system is based on the ray tracing (RT) visualization technique, the Sticks representation scheme (a data structure exploiting data coherence for the compression of classified data sets), the use of a slice‐partitioning technique for the distribution of the data between the processing nodes and the consequent ray‐data‐flow parallelizing strategy.

The system has been implemented on two different architectures: an inmos Transputer network and a hypercube nCUBE 6400 architecture. The high number of processors of this latter machine has allowed us to exploit a second level of parallelism (parallelism on image space, or parallelism on pixels) in order to arrive at a higher degree of scalability. In both proposals, the similarities between the chosen data‐partitioning strategy, the communications pattern of the visualization processes and the topology of the physical system architecture represent the key points and provide improved software design and efficiency. Moreover, the partitioning strategy used and the network interconnection topology reduce the communications overhead and allow for an efficient implementation of a static load‐balancing technique based on the prerendering of a low resolution image.

Details of the practical issues involved in the parallelization process of volumetric RT, commonly encountered problems (i.e. termination and deadlock prevention) and the sw migration process between different architectures are discussed.
Implementation of parallel algorithms for controlling robot manipulators
Authors: McKerrow P. J. , Fulcher J. A.
Published: November 2006

With the upsurge of interest in parallel processing during the 1980s, some researchers have applied such techniques indiscriminately, even in applications where little inherent concurrency exists. In the paper the kinematics of a 5‐DOF robot arm are investigated to assess the degree of parallelism contained within alternate robot models. This concurrency is mapped into occam processes, then control software generated to control the robot arm, firstly from a single transputer, then secondly from a network of transputers. On the basis of our findings, we conclude that there is limited parallelism which can be exploited in the Homogeneous transform model of the kinematics of a serial‐link manipulator. An alternative formulation of the kinematic model is required before much speed‐up can be achieved by parallel calculations. However, the architectures studied are suitable for modular manipulator systems, where joint transforms have to be calculated separately.
Model programs for computational science: A programming methodology for multicomputers
Authors: Hansen Per Brinch
Published: November 2006

We describe a programming methodology for computational science based on programming paradigms for multicomputers. Each paradigm is a class of algorithms that have the same control structure. For every paradigm, a general parallel program is developed. The general program is then used to derive two or more model programs, which solve specific problems in science and engineering. These programs have been tested on a Computing Surface and published with every detail open to scrutiny. We explain the steps involved in developing model programs and conclude that the study of programming paradigms provides an architectural vision of parallel scientific computing.
Parallel cellular automata: A model program for computational science
Authors: Hansen Per Brinch
Published: November 2006

We develop a model program for parallel execution of cellular automata on a multicomputer. The model program is then adapted for simulation of forest fires and numerical solution of Laplace's equation for stationary heat flow. The performance of the parallel program is analyzed and measured on a Computing Surface configured as a matrix of transputers with distributed memory.
Competitive neural networks on message‐passing parallel computers
Authors: Ceccarelli Michele , Petrosino Alfredo , Vaccaro Roberto
Published: November 2006

The paper reports two techniques for parallelizing on a MIMD multicomputer a class of learning algorithms (competitive learning) for artificial neural networks widely used in pattern recognition and understanding. The first technique presented, following the divide et impera strategy, achieves O(n/p + logP) time for n neurons and P processors interconnected as a tree. A modification of the algorithm allows the application of a systolic technique with the processors interconnected as a ring; this technique has the advantage that the communication time does not depend on the number of processors. The two techniques are also compared on the basis of predicted and measured performance on a transputer‐based MIMD machine. As the number of processors grows the advantage of the systolic approach increases. On the contrary, the divide et impera approach is more advantageous in the retrieving phase.
Global communications on locally connected message‐passing parallel computers
Authors: Debbage Mark , Hill Mark B. , Nicole Denis A.
Published: November 2006

Modern multicomputer components such as the inmos T800 and the Texas Instruments TMS320C40 provide hardware which supports efficient communication between directly connected processors. The paper describes techniques which have been developed to provide efficientglobalcommunications for machines based on these and similar processors. This service is implemented by a packet‐routing kernel adopting a standard, portable communications interface. The design of this kernel is discussed with particular emphasis on the manner in which it guarantees reliable, lightweight, deadlock‐free communication for arbitrary interconnection topologies. The kernel has been developed and tested on transputers. Extensive results on the performance of the router are presented to demonstrate that the substantial advantages associated with its well founded, structured design are not at odds with high efficiency. This router has been used to support several multi‐transputer environments, including a commercially available POSIX‐conformant operating system and a distributed occam environment freed from conventional configuration constraints.
Tmon: A performance monitor for transputer‐based multicomputers
Authors: Wagner A. , Jiang J. , Chanson S.
Published: November 2006

The paper describes a new performance monitoring tool, calledTmon, that has been developed to help application programmers understand the run‐time behavior of a parallel system and tune the performance of their programs. Tmon measures resource utilization and traces process activities transparently during execution. A global interrupt technique used by Tmon allows measurement tasks to be executed simultaneously on different processors and an accurate global clock to be maintained with minimal overhead. Experimental results indicate that both the accuracy and the overhead of the monitor are well within an acceptable range. We introduce a performance model from which it is possible to derive several different parallel programming metrics. A weighted critical path analysis tool is also presented that focusses the user's attention on those parts of the program whose modification would most improve performance. An example in which the tool is used successfully to improve the performance of a parallel application is also presented. Tmon is currently implemented on top of the Trollius Operating System and runs on a 74‐node transputer‐based multicomputer.
Monitoring and visualizing multiprocessor interconnection network contention
Authors: Zhang Hiaodong , Wang Beichang
Published: November 2006

Multistage Interconnection Networks (MIN) have been widely used for building large‐scale shared‐memory multiprocessor systems. Complex interactions between many processors and memory modules through the MIN, (such as interprocessor communication, process scheduling and synchronization and remote‐memory access) result in a significantly large space of possible performance behavior and potential performance bottlenecks. To provide insight into dynamic system performance, we have developed an integrated data collection, analysis, and visualization environment for a MIN‐based multiprocessor system, called MIN‐Graph. The MIN‐Graph is a graphical instrumentation monitor to aid users in investigating performance problems and in determining an effective way to exploit the high performance capabilities of interconnection network multiprocessor systems. Interconnection network contention is a major bottleneck of parallel computing on MIN‐based multiprocessors. This paper focuses on evaluating the contention behavior through performance monitoring and visualization. Four sets of system and scientific application programs with different programming and scheduling models and different memory access patterns are monitored and tested to observe the various network contention behaviors. The MIN‐Graph is implemented on the BBN GP1000 and the BBN TC2000.
Parallel simulation based on conservative time windows: A performance study
Authors: Ayani Rassul. , Rajaei Hassan
Published: November 2006

The paper presents a Conservative Time Window (CTW) algorithm for parallel simulation of discrete event systems. The physical system to be simulated is partitioned intondisjoint sub‐systems, each of which is represented by an object The CTW algorithm identifies a time window for each object, such that events occurring in each window are independent of events in other windows and thus they can be processed concurrently. The CTW algorithm was implemented on a shared memory multiprocessor, a Sequent Symmetry S81 with 16 processors. We measured performance of the CTW algorithm on two types of network topologies: feed‐forward networks and networks with feedback loops. We used three metrics to measure performance: speed‐up, average number of independent windows detected by the algorithm, and average number of events occurring in each window. We also investigated the impact of various event scheduling policies on performance. The results obtained show that the CTW algorithm produces good performance in many cases.
Performance modeling of load‐balancing algorithms using neural networks
Authors: Ahmad Ishfaq , Mehrotra Kishan , Mohan Chilukuri K. , Ranka Sanjay , Ghafoor Arif
Published: November 2006

The paper presents a new approach that uses neural networks to predict the performance of a number of dynamic decentralized load‐balancing strategies. A distributed multicomputer system using distributed load‐balancing strategies is represented by a unified analytical queuing model. A large simulation data set is used to train a neural network using the back‐propagation learning algorithm based on gradient descent The performance model using the predicted data from the neural network produces the average response time of various load balancing algorithms under various system parameters. The validation and comparison with simulation data show that the neural network is very effective in predicting the performance of dynamic load‐balancing algorithms. Our work leads to interesting techniques for designing load balancing schemes (for large distributed systems) that are computationally very expensive to simulate. One of the important findings is that performance is affected least by the number of nodes, and most by the number of links at each node in a large distributed system.
Global synchronisation in Linda
Authors: Butcher Paul , Wood Alan , Atkins Martin
Published: November 2006

The paper examines the ‘Distributed Summation’ problem, and its solution in Linda. A number of problems with the current set of primitives are examined, and a new primitive, collect, is proposed.
Time‐parallel solution of linear partial differential equations on the Intel Touchstone Delta supercomputer
Authors: Toomarian Nikzad , Fijany Amir , Barmen Jacob
Published: November 2006

The paper presents the implementation of a new class of massively parallel algorithms for solving certain time‐dependent partial differential equations (PDEs) on massively parallel supercomputers. Such PDEs are usually solved numerically, by discretization in time and space, and by applying a time‐stepping procedure to data and algorithms potentially parallelized in the spatial domain. In a radical departure from such a strictly sequential temporal paradigm, we have developed a concept of time‐parallel algorithms, which allows the marching in time to be fully parallelized. This is achieved by using a set of transformations based on eigenvalue‐eigenvector decomposition of the matrices involved in the discrete formalism. Our time‐parallel algorithms possess a highly decoupled structure, and can therefore be efficiently implemented on emerging, massively parallel, high‐performance supercomputers, with a minimum of communication and synchronization overhead. We have successfully carried out a proof‐of‐concept demonstration of the basic ideas using a two‐dimensional heat equation example implemented on the Intel Touchstone Delta supercomputer. Our results indicate that linear, and even superlinear, speed‐up can be achieved and maintained for a very large number of processor nodes.
Dynamic load‐balancing for PDE solvers on adaptive unstructured meshes
Authors: Walshaw Chris , Berzins Martin
Published: November 2006

Modern PDE solvers written for time‐dependent problems increasingly employ adaptive unstructured meshes (Flaherty et al., 1989) in order to both increase efficiency and control the numerical error. If a distributed memory parallel computer is to be used, there arises the significant problem of dividing the domain equally amongst the processors whilst minimising the inter‐subdomain dependencies. A number of graph‐based algorithms have recently been proposed for steady‐state calculations. The paper considers an extension to such methods which renders them more suitable for time‐dependent problems in which the mesh may be changed frequently.
SCIDDLE: A tool for large scale distributed computing
Authors: Arbenz Peter , Sprenger Christoph , Luthi Hans Peter , Vogel Stefan
Published: November 2006

We report on a portable communication environment, ‘SCIDDLE’, for distributing computations over heterogenous networks of UNIX computers. SCIDDLE is based on the client‐server model. It was designed to support the distribution of large scale numerical computations and to keep its usage as simple as possible. All interprocess communication is done via remote procedure calls. The user defines the interface between communicating processes in a simple declarative language. Parallel programming is supported by asynchronous RPCs. A convenient array handing has been implemented. We demonstrate the usefulness of the system with an application from quantum chemistry on internet‐connected workstations and supercomputers.
Comparative study of task duplication static scheduling versus clustering and non‐clustering techniques
Authors: Shirazi Behrooz , Chen Hsing‐Bung , Marquis Jeff
Published: November 2006

One of the major issues that needs to be addressed in distributed memory multiprocessor (DMM) systems is the program task partitioning and scheduling problems, i.e. mapping of an application program's precedence related task threads among the processing elements of a DMM system. The optimal task partitioning and scheduling problem, with the goal of minimizing the program execution time and interprocessor communication overhead, is known to be an NP‐complete problem. The paper addresses the design, development and performance evaluation of a novel static task partitioning and scheduling method called linear clustering with task duplication (LCTD). LCTD employs the linear (sequential) execution of tasks and task duplication heuristics in achieving minimized computation and interprocessor communication delays in DMMs. The superiority of the proposed LCTD algorithm is demonstrated through simulation studies and comparison against several of the existing static scheduling schemes, such as heavy node first (HNF) and linear clustering. We show that the proposed method can obtain an average of 33% improvement in program execution time and 21% improvement in processor utilization compared to linear clustering and HNF methods.
A fast recursive mapping algorithm
Authors: Chen Song , Eshaghian Mary M.
Published: November 2006

The paper presents a generic technique for mapping parallel algorithms onto parallel architectures. The proposed technique is a fast recursive mapping algorithm which is a component of the Cluster‐M programming tool. The other components of Cluster‐M are the Specification module and the Representation module. In the Specification module, for a given task specified by a high‐level machine‐independent program, a clustered task graph called Spec graph is generated. In the Representation module, for a given architecture or computing organization, a clustered system graph called Rep graph is generated. Given a task (or system) graph, a Spec (or Rep) graph can be generated using one of the clustering algorithms presented in the paper. The clustering is done only once for a given task graph (system graph) independent of any system graphs (task graphs). It is a machine‐independent (application‐independent) clustering, and therefore it is not repeated for different mappings. The Cluster‐M mapping algorithm presented produces a sub‐optimal matching of a given Spec graph containing M task modules, onto a Rep graph of N processors, in O(MN) time. This generic algorithm is suitable for both the allocation problem and the scheduling problem. Its performance is compared to other leading techniques. We show that Cluster‐M produces better or similar results in significantly less time and using fewer or an equal number of processors as compared to the other known methods.
Task assignment using a problem‐space genetic algorithm
Authors: Ahmad Imtiaz , Dhodhi Muhammad K.
Published: November 2006

The task assignment problem is one of assigning tasks of a parallel program among the processors of a distributed computing system in order to reduce the job turnaround time and to increase the throughput of the system. Since the task assignment problem is known to be NP‐complete except in a few special situations, satisfactory suboptimal solutions obtainable in a reasonable amount of computation time are generally sought. In the paper we introduce a technique based on the problem‐space genetic algorithm (PSGA) for the static task assignment problem in both homogeneous and heterogeneous distributed computing systems to reduce the task turnaround time and to increase the throughput of the system by properly balancing the load and reducing the interprocessor communication time among processors. The PSGA based approach combines the power of genetic algorithms, a global search method, with a simple and fast problem‐specific heuristic to search a large solution space efficiently and effectively to find the best possible solution in an acceptable CPU time. Experimental results on test examples from the literature show considerable improvements in both the assignment cost and the CPU times over the previous work. The proposed scheme is also applied to a digital signal processing (DSP) system consisting of 119 tasks to illustrate its balancing properties and computational advantage on a large system. The proposed scheme offers 12–30% improvement in the assignment cost as compared to the previous best known results for the DSP example.
A partitioning advisory system for networked data‐parallel processing
Authors: Crandall Phyllis E. , Quinn Michael J.
Published: November 2006

With the increased performance capabilities of desktop computers, networked computing has become a popular vehicle for using parallelism to solve a variety of computationally intense problems. However, node heterogeneity and high communication costs may limit performance unless the problem space is carefully partitioned across the network in a way that considers both the capabilities of the machines and the high network communication costs. We describe an advisory system that is designed to help the programmer, compiler or run‐time environment choose the best decomposition strategy for partitioning specific data‐parallel applications across a given collection of machines. The system includes provisions for assessing the capabilities of the participating machines and the network in light of the current workload. Given information about the problem space, the machine speeds and the network, the system provides a ranking of three standard partitioning methods. We test the validity of our system by comparing the observed relative performance with predicted relative performance of different data decompositions on a program with a variable number of floating point operations and a 5‐point stencil communication pattern.
Beyond software performance visualization
Authors: Abrams M. , Lee T. J. , Cadiz H. T. , Ganugapati K.
Published: November 2006

Performance visualization tools of the past decade have yielded new insights into the behavior of sequential, parallel and distributed programs. However, they have three inherent limitations: (1) they only display what happened in one execution of a program (this is dangerous when analyzing concurrent applications, which are prone to non‐deterministic behavior); (2) a human uses one or more bandwidth‐limited senses with a visualization tool (this limits the scalability of a visualization tool); (3) the relationship of ‘interesting’ program events is often separated in time by other events; thus discerning time‐dependent behavior often hinges on finding the ‘right’ visualization—a possibly time‐consuming activity. CHITRA93 complements visualization systems, while alleviating these limitations, and analyzes a set (or ensemble) of traces by combining the visualization of a few traces with a statistical analysis of the entire ensemble (overcoming (1)). It reduces the ensemble to empirical models that capture the time‐dependent relationships of ‘interesting’ program events through application, programming language and computer architecture independent analysis techniques (addressing (2) and (3)). It also incorporates the following transforms, such as aggregation, that simplify the ensemble and reduce the state‐space size of the models generated; a user interface that allows certain transforms to be selected by editing the visualization with a mouse; homogeneity tests that allow partitioning of an ensemble; an efficient semi‐Markov model generation algorithm whose computation time is linear in the sum of the lengths of the traces comprising the ensemble; and a CHAID‐based model that can fathom non‐Markovian relationships among transitions in the traces. The use of CHITRA93 is demonstrated by partitioning ten parallel database traces with nearly 8,000 states into two homogeneous subsets, each modeled by an irreducible, periodic and hierarchical stochastic process with as few as four states.
A toolkit for parallel functional programming
Authors: Hartel Pieter H. , Hofman Rutger F. H. , Langendoen Koen G. , Muller Henk L. , Vree Willem G. , Hertzberger L. O.
Published: November 2006

Our toolkit for the design and implementation of parallel functional programs supports the stepwise development of parallel programs from a high level sequential specification to an optimised parallel implementation. The toolkit is used as follows:

The algorithm to be implemented is specified in a functional language. The program is debugged and tested using an interpreter.

The program is compiled for a sequential machine. Its performance is analysed and improved.

Annotation‐driven transformations are applied to the program to indicate parallel tasks. Simulations at task level, basic block level and bus transaction level make it possible to analyse the parallel performance of the program at three levels of detail.

When the performance is optimised using the simulators, the program is executed on a genuine parallel machine.

Several programs have been developed with the toolkit. A program that simulates tidal flow in an estuary of the North sea is presented as a case study to demonstrate the merits of the toolkit when developing complex parallel programs.

The toolkit not only supports the design of parallel applications, it also allows the study of important concepts in parallel computer architecture. These include the behaviour of cached memory systems, bus protocols, scheduling algorithms and memory management algorithms.
Unfolding Tin–Cobalt Interactions in Oxide‐Based Composite Electrodes for Li‐Ion Batteries by Mössbauer Spectroscopy
Authors: Alcántara Ricardo , Ortiz Gregorio F. , Tirado José L.
Published: November 2006

With a view to the development of new composite electrodes for lithium‐ion batteries with electroactive tin and cobalt, Co‐doped tin dioxide samples are studied. The role played by oxygen and cobalt atoms in the electrochemical behavior of tin‐based electrodes for Li‐ion batteries is examined by the powerful and selective 119Sn Mössbauer spectroscopy. For the discharged electrodes, the oxygen atoms in the lithia matrix tend to destabilize the Sn(0) atoms. In contrast, the presence of cobalt atoms helps to form a matrix that stabilizes the reduced tin atoms. Cobalt–tin interactions in electrochemical reduced CoxSn1−xO2 electrodes are deduced from the electrochemical and Mössbauer results.
Electrochemical Microstructuring with Short Voltage Pulses
Authors: Schuster Rolf
Published: November 2006

The application of short (nanosecond) voltage pulses between a tool electrode and a workpiece immersed in an electrolyte solution allows the three‐dimensional machining of electrochemically active materials with submicrometer resolution. The method is based on the finite charging time constant of the double‐layer capacitance, which varies approximately linearly with the local separation between the electrode surfaces. Hence, the polarization of the electrodes during short pulses and subsequent electrochemical reactions are confined to regions where the electrodes are in sufficiently close proximity. This Minireview describes the principles behind electrochemical microstructuring with short voltage pulses, and its current achievements and limitations.
Flow‐assisted quantification of in vitro activated basophils in the diagnosis of wasp venom allergy and follow‐up of wasp venom immunotherapy
Authors: Ebo D. G. , Hagendorens M. M. , Schuerwegh A. J. , Beirens L. M.‐N. , Bridts C. H. , De Clerck L. S. , Stevens W. J.
Published: November 2006

Background:

Correct identification of the culprit venom is a prerequisite for specific venom immunotherapy (VIT). Despite the efficacy of VIT, issues as how to monitor treatment and when to discontinue maintenance therapy remain to be established.

Methods:

To evaluate diagnostic performances of the basophil activation test (BAT) in wasp venom allergy, 80 patients with a definite history of wasp venom anaphylaxis (systemic reactors) and 14 wasp‐stung asymptomatic controls (stung controls) were enrolled. Venom‐induced basophil activation was analyzed flow cytometrically by double‐labeling with anti‐IgE and anti‐CD63. Results were compared to wasp IgE levels and results of a venom skin test (VST). To establish whether the BAT constitutes a candidate marker to monitor VIT, the BAT was repeated in 22 patients on the 5th day of a build‐up course and after 6 months of maintenance VIT. Whether the BAT could contribute in the decision of discontinuing VIT was assessed in a cross‐sectional analysis in 30 patients receiving treatment for 3 years.

Results:

Comparison between systemic reactors and stung controls revealed a sensitivity of 86.4% and specificity of 100% for venom IgE, and sensitivity of 81.8% for VST, respectively. In contrast to stung controls, patients demonstrated dose‐dependent venom‐induced basophil activation. The BAT attained a sensitivity of 83.8% and specificity of 100%. At the end of the build‐up course, no effect of VIT on the BAT was demonstrable. When the BAT was repeated after 6 months of treatment, submaximal stimulation of the cells demonstrated a significant decreased CD63 expression (P < 0.04). Patients having VIT for 3 years also demonstrated significantly lower venom‐induced CD63 expression (P < 0.001). After 3 years, 60% of the patients had a negative BAT for submaximal stimulation of the cells whereas only 17.9% of the patients had negativation of wasp IgE.

Conclusions:

The BAT is a reliable instrument for the diagnosis of wasp venom anaphylaxis and might constitute an instrument to monitor wasp VIT. © 2006 International Society for Analytical Cytology