Search

Wireless Network-on-Chip (WNoC) is a promising concept which provides a solution to overcome the scalability issues in prevailing networks-in-package for many-core processors. However, the electromagnetic propagation inside the chip package leads to energy reverberation, resulting in Inter-Symbol Interference (ISI) with high delay spreads. Time Reversal (TR) is a technique that benefits the unique time-invariant channel with rich multipath effects to focus the energy to the desired transceiver. TR mitigates both ISI and co-channel interference, hence providing parallel communications in both space and time. Thus, TR is a versatile candidate to improve the aggregate bandwidth of wireless on-chip networks provided that a Medium Access Control (MAC) is used to efficiently share the wireless medium. In this paper, we explore a simple yet resilient TR-based MAC protocol (TR-MAC) design for WNoC. We propose to manage multiple parallel transmissions with simultaneous spatial channels in the same time slot with TR precoding and focused energy detection at the transceiver. Our results show that TR-MAC can be employed in massive computing architectures with improved latency and throughput while matching with the stringent requirements of the physical layer.

We present PolarStar, a novel family of diameter-3 network topologies derived from the star product of low-diameter factor graphs. PolarStar gives the largest known diameter-3 network topologies for almost all radixes, thus providing the best known scalable diameter-$3$ network. Compared to current state-of-the-art diameter-$3$ networks, PolarStar achieves $1.3\times$ geometric mean increase in scale over Bundlefly, $1.9\times$ over Dragonfly, and $6.7\times$ over {3-D} HyperX. PolarStar has many other desirable properties, including a modular layout, large bisection, high resilience to link failures and a large number of feasible configurations for every radix. We give a detailed evaluation with simulations of synthetic and real-world traffic patterns and show that PolarStar exhibits comparable or better performance than current diameter-3 networks., Comment: 13 pages, published in SPAA 2024

We have previously defined synchronization (Gomez, E. and K. Schubert 2011) as a relation between the times at which a pair of events can happen, and introduced an algebra that covers all possible relations for such pairs. In this work we introduce the synchronization matrix, to make it easier to calculate the properties and results of $N$ event synchronizations, such as are commonly encountered in parallel execution of multiple processes. The synchronization matrix leads to the definition of N-event synchronization algebras as specific extensions to the original algebra. We derive general properties of such synchronization, and we are able to analyze effects of synchronization on the phase space of parallel execution introduced in (Gomez E Kai R, Schubert KE 2017), Comment: 9 pages, 2 figures

In this paper we present PolarFly, a diameter-2 network topology based on the Erdos-Renyi family of polarity graphs from finite geometry. This is a highly scalable low-diameter topology that asymptotically reaches the Moore bound on the number of nodes for a given network degree and diameter PolarFly achieves high Moore bound efficiency even for the moderate radixes commonly seen in current and near-future routers, reaching more than 96% of the theoretical peak. It also offers more feasible router degrees than the state-of-the-art solutions, greatly adding to the selection of scalable diameter-2 networks. PolarFly enjoys many other topological properties highly relevant in practice, such as a modular design and expandability that allow incremental growth in network size without rewiring the whole network. Our evaluation shows that PolarFly outperforms competitive networks in terms of scalability, cost and performance for various traffic patterns., Comment: In Proceedings of International Conference for High Performance Computing, Networking, Storage, and Analysis (SC) 2022

Network-on-chip (NoC) architectures rely on buffers to store flits to cope with contention for router resources during packet switching. Recently, reversible multi-function channel (RMC) buffers have been proposed to simultaneously reduce power and enable adaptive NoC buffering between adjacent routers. While adaptive buffering can improve NoC performance by maximizing buffer utilization, controlling the RMC buffer allocations requires a congestion-aware, scalable, and proactive policy. In this work, we present RACE, a novel reinforcement learning (RL) framework that utilizes better awareness of network congestion and a new reward metric ("falsefulls") to help guide the RL agent towards better RMC buffer control decisions. We show that RACE reduces NoC latency by up to 48.9%, and energy consumption by up to 47.1% against state-of-the-art NoC buffer control policies., Comment: 6 pages, 8 figures, 3 tables

The growth of the Internet and its associated technologies; including digital services have tremendously impacted our society. However, scholars have noted a trend in data flow and collection; and have alleged mass surveillance and digital supremacy. To this end therefore, nations of the world such as Russia, China, Germany, Canada, France and Brazil among others have taken steps toward changing the narrative. The question now is, should Africans join these giants in this school of thought on digital sovereignty or fold their hands to remain on the other side of the divide? This question among others are the main reasons that provoked the thoughts of putting this paper together. This is with a view to demystifying the strategies to reconfigure data infrastructure in the context of Africa. It also highlights the benefits of digital technologies and its propensity to foster all round development in the continent as it relates to economic face-lift, employment creation, national security, among others. There is therefore a need for African nations to design appropriate blueprint to ensure security of her digital infrastructure and the flow of data within her cyber space. In addition, a roadmap in the immediate, short- and long-term in accordance with the framework of African developmental goals should be put in place to guide the implementation., Comment: 7 pages

The allreduce operation is one of the most commonly used communication routines in distributed applications. To improve its bandwidth and to reduce network traffic, this operation can be accelerated by offloading it to network switches, that aggregate the data received from the hosts, and send them back the aggregated result. However, existing solutions provide limited customization opportunities and might provide suboptimal performance when dealing with custom operators and data types, with sparse data, or when reproducibility of the aggregation is a concern. To deal with these problems, in this work we design a flexible programmable switch by using as a building block PsPIN, a RISC-V architecture implementing the sPIN programming model. We then design, model, and analyze different algorithms for executing the aggregation on this architecture, showing performance improvements compared to state-of-the-art approaches.

Optical networks with multi-core fibers can replace several electronics networks with a single topology. Each electronic link is replaced by a single fiber, which can save space, weight, and cost, while having better segregation and EMI resistance. This is, for instance, of high interest in safety-critical cyber-physical systems, such as aircraft avionics networks. Finding the optimal topology requires finding the optimal number of components, component locations, inter-meshing, and signal routing, while assuring the appropriate optical power level at each participating device. A Mixed-integer Linear Programming (MILP) representation is presented for the optimization of the topology of optical multi-core fiber networks. The optimization approach retrieves a globally optimal topology with respect to weight or cost, i.e. it builds the optimal network topology from a set of switch and cable types, which differ in the number of fibers, attenuation, connectors, and other properties. The novelty of our approach is the consideration of translucent and opaque optical switches as well as the representation of cable and device attenuation directly in the MILP constraints. Moreover, arbitrary installation and routing resource restrictions are considered. The application of the approach to five dedicated scenarios yields in each case an optimal solution and validates our method. The application to an excerpt of an aircraft cabin network shows the retrieval of the global optimum in less 30 min for a topology with 48 signals and 23 components., Comment: changes: typos corrected, figure and table formating improved 18 pages, 15 figures, 13 tables

On-chip communication infrastructure is a central component of modern systems-on-chip (SoCs), and it continues to gain importance as the number of cores, the heterogeneity of components, and the on-chip and off-chip bandwidth continue to grow. Decades of research on on-chip networks enabled cache-coherent shared-memory multiprocessors. However, communication fabrics that meet the needs of heterogeneous many-cores and accelerator-rich SoCs, which are not, or only partially, coherent, are a much less mature research area. In this work, we present a modular, topology-agnostic, high-performance on-chip communication platform. The platform includes components to build and link subnetworks with customizable bandwidth and concurrency properties and adheres to a state-of-the-art, industry-standard protocol. We discuss microarchitectural trade-offs and timing/area characteristics of our modules and show that they can be composed to build high-bandwidth (e.g., 2.5 GHz and 1024 bit data width) end-to-end on-chip communication fabrics (not only network switches but also DMA engines and memory controllers) with high degrees of concurrency. We design and implement a state-of-the-art ML training accelerator, where our communication fabric scales to 1024 cores on a die, providing 32 TB/s cross-sectional bandwidth at only 24 ns round-trip latency between any two cores., Comment: 14 pages, 24 figures, 4 tables

Swarm robotic systems are currently being used to address many real-world problems. One interesting application of swarm robotics is the self-organized formation of structures and shapes. Some of the key challenges in the swarm robotic systems include swarm size constraint, random motion, coordination among robots, localization, and adaptability in a decentralized environment. Rubenstein et al. presented a system ("Programmable self-assembly in a thousand-robot swarm", Science, 2014) for thousand-robot swarm able to form only solid shapes with the robots in aggregated form by applying the collective behavior algorithm. Even though agent-based approaches have been presented in various studies for self-organized formation, however these studies lack agent-based modeling (ABM) approach along with the constraints in term of structure complexity and heterogeneity in large swarms with dynamic localization. The cognitive agent-based computing (CABC) approach is capable of modeling such self-organization based multi-agents systems (MAS). In this paper, we develop a simulation model using ABM under CABC approach for self-organized shape formation in swarm robots. We propose a shape formation algorithm for validating our model and perform simulation-based experiments for six different shapes including hole-based shapes. We also demonstrate the formal specification for our model. The simulation result shows the robustness of the proposed approach having the emergent behavior of robots for the self-organized shape formation. The performance of the proposed approach is evaluated by robots convergence rate., Comment: 40 pages

We implement and benchmark parallel I/O methods for the fully-manycore driven particle-in-cell code PIConGPU. Identifying throughput and overall I/O size as a major challenge for applications on today's and future HPC systems, we present a scaling law characterizing performance bottlenecks in state-of-the-art approaches for data reduction. Consequently, we propose, implement and verify multi-threaded data-transformations for the I/O library ADIOS as a feasible way to trade underutilized host-side compute potential on heterogeneous systems for reduced I/O latency., Comment: 15 pages, 5 figures, accepted for DRBSD-1 in conjunction with ISC'17

As we move towards an era of hundreds of cores, the research community has witnessed the emergence of opto-electronic network on-chip designs based on nanophotonics, in order to achieve higher network throughput, lower latencies, and lower dynamic power. However, traditional nanophotonics options face limitations such as large device footprints compared with electronics, higher static power due to continuous laser operation, and an upper limit on achievable data rates due to large device capacitances. Nanoplasmonics is an emerging technology that has the potential for providing transformative gains on multiple metrics due to its potential to increase the light-matter interaction. In this paper, we propose and analyze a hybrid opto-electric NoC that incorporates Hybrid Plasmonics Photonics Interconnect (HyPPI), an optical interconnect that combines photonics with plasmonics. We explore various opto-electronic network hybridization options by augmenting a mesh network with HyPPI links, and compare them with the equivalent options afforded by conventional nanophotonics as well as pure electronics. Our design space exploration indicates that augmenting an electronic NoC with HyPPI gives a performance to cost ratio improvement of up to 1.8x. To further validate our estimates, we conduct trace based simulations using the NAS Parallel Benchmark suite. These benchmarks show latency improvements up to 1.64x, with negligible energy increase. We then further carry out performance and cost projections for fully optical NoCs, using HyPPI as well as conventional nanophotonics. These futuristic projections indicate that all-HyPPI NoCs would be two orders more energy efficient than electronics, and two orders more area efficient than all-photonic NoCs., Comment: 10 pages, 8 figures

We present xDGDL, an approach towards a concise but comprehensive Datagrid description language. Our framework is based on the portable XML language and allows to store syntactical and semantical information together with arbitrary files. This information can be used to administer, locate, search and process the stored data on the Grid. As an application of the xDGDL approach we present ViPFS, a novel distributed file system targeting the Grid., Comment: accepted at 1st Workshop on Hardware/Software Support for Parallel and Distributed Scientific and Engineering Computing (SPDSEC-02) in conjunction with The 11th International Conference on Parallel Architectures and Compilation Techniques (PACT-02)

Hierarchical ring networks, which hierarchically connect multiple levels of rings, have been proposed in the past to improve the scalability of ring interconnects, but past hierarchical ring designs sacrifice some of the key benefits of rings by introducing more complex in-ring buffering and buffered flow control. Our goal in this paper is to design a new hierarchical ring interconnect that can maintain most of the simplicity of traditional ring designs (no in-ring buffering or buffered flow control) while achieving high scalability as more complex buffered hierarchical ring designs. Our design, called HiRD (Hierarchical Rings with Deflection), includes features that allow us to mostly maintain the simplicity of traditional simple ring topologies while providing higher energy efficiency and scalability. First, HiRD does not have any buffering or buffered flow control within individual rings, and requires only a small amount of buffering between the ring hierarchy levels. When inter-ring buffers are full, our design simply deflects flits so that they circle the ring and try again, which eliminates the need for in-ring buffering. Second, we introduce two simple mechanisms that provides an end-to-end delivery guarantee within the entire network without impacting the critical path or latency of the vast majority of network traffic. HiRD attains equal or better performance at better energy efficiency than multiple versions of both a previous hierarchical ring design and a traditional single ring design. We also analyze our design's characteristics and injection and delivery guarantees. We conclude that HiRD can be a compelling design point that allows higher energy efficiency and scalability while retaining the simplicity and appeal of conventional ring-based designs.

Memristors have been suggested as a novel route to neuromorphic computing based on the similarity between them and neurons (specifically synapses and ion pumps). The d.c. action of the memristor is a current spike which imparts a short-term memory to the device. Here it is demonstrated that this short-term memory works exactly like habituation (e.g. in \emph{Aplysia}). We elucidate the physical rules, based on energy conservation, governing the interaction of these current spikes: summation, `bounce-back', directionality and `diminishing returns'. Using these rules, we introduce 4 different logical systems to implement sequential logic in the memristor and demonstrate how sequential logic works by instantiating a NOT gate, an AND gate, an XOR gate and a Full Adder with a single memristor. The Full Adder makes use of the memristor's short-term memory to add together three binary values and outputs the sum, the carry digit and even the order they were input in. A memristor full adder also outputs the arithmetical sum of bits, allowing for a logically (but not physically) reversible system. Essentially, we can replace an input/output port with an extra time-step, allowing a single memristor to do a hither-to unexpectedly large amount of computation. This makes up for the memristor's slow operation speed and may relate to how neurons do a similarly-large computation with such slow operations speeds. We propose that using spiking logic, either in gates or as neuron-analogues, with plastic rewritable connections between them, would allow the building of a neuromorphic computer.

As high-performance computing (HPC) moves into the exascale era, computer scientists and engineers must find innovative ways of transferring and processing unprecedented amounts of data. As the scale and complexity of the applications running on these machines increases, the cost of their interactions and data exchanges (in terms of latency, energy, runtime, etc.) can increase exponentially. In order to address I/O coordination and communication issues, computing vendors are developing an intermediate layer between compute nodes and the parallel file system composed of different types of memory (NVRAM, DRAM, SSD). These large scale memory appliances are being called 'burst buffers.' In this paper, we envision advanced memory at various levels of HPC hardware and derive potential use cases for how to take advantage of it. We then present the challenges and issues that arise when utilizing burst buffers in next-generation supercomputers and map the challenges to the use cases. Lastly, we discuss the emerging state-of-the-art burst buffer solutions that are expected to become available by the end of the year in new HPC systems and which use cases these implementations may satisfy., Comment: 18 pages, 2 figures

The server-centric data centre network architecture can accommodate a wide variety of network topologies. Newly proposed topologies in this arena often require several rounds of analysis and experimentation in order that they might achieve their full potential as data centre networks. We propose a family of novel routing algorithms on two well-known data centre networks of this type, (Generalized) DCell and FiConn, using techniques that can be applied more generally to the class of networks we call completely connected recursively-defined networks. In doing so, we develop a classification of all possible routes from server-node to server-node on these networks, called general routes of order $t$, and find that for certain topologies of interest, our routing algorithms efficiently produce paths that are up to 16% shorter than the best previously known algorithms, and are comparable to shortest paths. In addition to finding shorter paths, we show evidence that our algorithms also have good load-balancing properties., Comment: Appeared at the 13th IEEE International Symposium on Parallel and Distributed Processing with Applications (IEEE ISPA-15)

DPillar has recently been proposed as a server-centric datacenter network and is combinatorially related to (but distinct from) the well-known wrapped butterfly network. We explain the relationship between DPillar and the wrapped butterfly network before proving that the underlying graph of DPillar is a Cayley graph; hence, the datacenter network DPillar is node-symmetric. We use this symmetry property to establish a single-path routing algorithm for DPillar that computes a shortest path and has time complexity $O(k)$, where $k$ parameterizes the dimension of DPillar (we refer to the number of ports in its switches as $n$). Our analysis also enables us to calculate the diameter of DPillar exactly. Moreover, our algorithm is trivial to implement, being essentially a conditional clause of numeric tests, and improves significantly upon a routing algorithm earlier employed for DPillar. Furthermore, we provide empirical data in order to demonstrate this improvement. In particular, we empirically show that our routing algorithm improves the average length of paths found, the aggregate bottleneck throughput, and the communication latency. A secondary, yet important, effect of our work is that it emphasises that datacenter networks are amenable to a closer combinatorial scrutiny that can significantly improve their computational efficiency and performance., Comment: Accepted in IEEE Transactions on Parallel & Distributed Systems, July 2016

In this paper, we use the language of operads to study open dynamical systems. More specifically, we study the algebraic nature of assembling complex dynamical systems from an interconnection of simpler ones. The syntactic architecture of such interconnections is encoded using the visual language of wiring diagrams. We define the symmetric monoidal category W, from which we may construct an operad O(W), whose objects are black boxes with input and output ports, and whose morphisms are wiring diagrams, thus prescribing the algebraic rules for interconnection. We then define two W-algebras, G and L, which associate semantic content to the structures in W. Respectively, they correspond to general and to linear systems of differential equations, in which an internal state is controlled by inputs and produces outputs. As an example, we use these algebras to formalize the classical problem of systems of tanks interconnected by pipes, and hence make explicit the algebraic relationships among systems at different levels of granularity., Comment: 26 pages

Data centers have been evolved from a passive element of compute infrastructure to become an active, core part of any ICT solution. In particular, modular data centers (MDCs), which are a promising design approach to improve resiliency of data centers, can play a key role in deploying ICT infrastructure in remote and inhospitable environments in order to take advantage of low temperatures and hydro- and wind-electric capabilities. This is because of capability of the modular data centers to survive even in lack of continuous on-site maintenance and support. The most critical part of a data center is its network fabric that could impede the whole system even if all other components are fully functional, assuming that other analyses has been already performed to ensure the reliability of the underlying infrastructure and support systems. In this work, a complete failure analysis of modular data centers using failure models of various components including servers, switches, and links is performed using a proposed Monte-Carlo approach. The proposed Monte-Carlo approach, which is based on the concept of snapshots, allows us to effectively calculate the performance of a design along its lifespan even up to the terminal stages. To show the capabilities of the proposed approach, various network topologies, such as FatTree, BCube, MDCube, and their modifications are considered. The performance and also the lifespan of each topology design in presence of failures of their components are studied against the topology parameters., Comment: 29 Pages, 14 figures

Thin films containing casein appear to be a promising material for coatings used in the medical area to promote biomineralization. alfa- and beta-casein and poly-L-arginine multilayer films were formed by the layer-by layer technique and their thickness and mass were analyzed by ellipsometry and quartz crystal microbalance with dissipation monitoring (QCM-D). We investigated the effect of the type of casein used for the film formation and of the polyethyleneimine anchoring layer on the thickness and mass of adsorbed films. The analysis of the mass of films during their post-treatment with the solutions of various ionic strength and pH provided the information concerning films stability, while the XPS elemental analysis confirmed binding of calcium ions by the casein embedded in the multilayers., Comment: 7 pages, 10 figures, prepared to publish in Journal of Colloid and Interface Science

We introduce an analytical framework to understand the path for scaling nanophotonic interconnects to meet the energy and footprint requirements of CMOS global interconnects. We derive the device requirements for sub 100 fJ/cm/bit interconnects including tuning power, serialization-deserialization energy, optical insertion losses, extinction ratio and bit error rates. Using CMOS with integrated nanophotonics as an example platform, we derive the energy/bit, linear and areal bandwidth density of optical interconnects. We also derive the targets for device performance which indicate the need for continued improvements in insertion losses (<8dB), laser efficiency, operational speeds (>40 Gb/s), tuning power (<100 {\mu}W/nm), serialization-deserialization (< 10 fJ/bit/Operation) and necessity for spectrally selective devices with wavelength multiplexing (> 6 channels)., Comment: Accepted to IEEE Journal of Special Topics in Quantum Electronics

We formalise a general concept of distributed systems as sequential components interacting asynchronously. We define a corresponding class of Petri nets, called LSGA nets, and precisely characterise those system specifications which can be implemented as LSGA nets up to branching ST-bisimilarity with explicit divergence.

When considering distributed systems, it is a central issue how to deal with interactions between components. In this paper, we investigate the paradigms of synchronous and asynchronous interaction in the context of distributed systems. We investigate to what extent or under which conditions synchronous interaction is a valid concept for specification and implementation of such systems. We choose Petri nets as our system model and consider different notions of distribution by associating locations to elements of nets. First, we investigate the concept of simultaneity which is inherent in the semantics of Petri nets when transitions have multiple input places. We assume that tokens may only be taken instantaneously by transitions on the same location. We exhibit a hierarchy of `asynchronous' Petri net classes by different assumptions on possible distributions. Alternatively, we assume that the synchronisations specified in a Petri net are crucial system properties. Hence transitions and their preplaces may no longer placed on separate locations. We then answer the question which systems may be implemented in a distributed way without restricting concurrency, assuming that locations are inherently sequential. It turns out that in both settings we find semi-structural properties of Petri nets describing exactly the problematic situations for interactions in distributed systems., Comment: 26 pages. An extended abstract of this paper appeared in Proceedings 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), Torun, Poland, August 2008 (E. Ochmanski & J. Tyszkiewicz, eds.), LNCS 5162, Springer, 2008, pp. 16-35

We investigate classes of systems based on different interaction patterns with the aim of achieving distributability. As our system model we use Petri nets. In Petri nets, an inherent concept of simultaneity is built in, since when a transition has more than one preplace, it can be crucial that tokens are removed instantaneously. When modelling a system which is intended to be implemented in a distributed way by a Petri net, this built-in concept of synchronous interaction may be problematic. To investigate this we consider asynchronous implementations of nets, in which removing tokens from places can no longer be considered as instantaneous. We model this by inserting silent (unobservable) transitions between transitions and some of their preplaces. We investigate three such implementations, differing in the selection of preplaces of a transition from which the removal of a token is considered time consuming, and the possibility of collecting the tokens in a given order. We investigate the effect of these different transformations of instantaneous interaction into asynchronous interaction patterns by comparing the behaviours of nets before and after insertion of the silent transitions. We exhibit for which classes of Petri nets we obtain equivalent behaviour with respect to failures equivalence. It turns out that the resulting hierarchy of Petri net classes can be described by semi-structural properties. For two of the classes we obtain precise characterisations; for the remaining class we obtain lower and upper bounds. We briefly comment on possible applications of our results to Message Sequence Charts., Comment: 27 pages. An extended abstract of this paper was presented at the first Interaction and Concurrency Experience (ICE'08) on Synchronous and Asynchronous Interactions in Concurrent Distributed Systems, and will appear in Electronic Notes in Theoretical Computer Science, Elsevier

Off-chip buses account for a significant portion of the total system power consumed in embedded systems. Bus encoding schemes have been proposed to minimize power dissipation, but none has been demonstrated to be optimal with respect to any measure. In this paper, we give the first provably optimal and explicit (polynomial-time constructible) families of memoryless codes for minimizing bit transitions in off-chip buses. Our results imply that having access to a clock does not make a memoryless encoding scheme that minimizes bit transitions more powerful., Comment: Proceedings of the 2006 IEEE/ACM international Conference on Computer-Aided Design (San Jose, California, November 05 - 09, 2006). ICCAD '06. ACM, New York, NY, 369-374

Problems of the switching parallel system designing provided spatial switching of packets from random time are discussed. Results of modeling of switching system as systems of mass service are resulted., Comment: 3 pages, 2 figure

The transmission of electric signals on a coupled line with distributed RLC-parameters is considered as a propagation of a dissipative quasi particle. A calculation technique is developed, alternative to the one, accepted for lumped lines. The relativistic wave equation for the transient response is deduced following the common Ohm-low-type considerations. The exact expressions for the Green function, for information transfer velocity and for time delay are obtained on this base. The fundamental restrictions on the measurement accuracy of the time delay are pointed out. The obtained results are naturally generalized for the multilevel networks of the arbitrary dimension., Comment: 6 pages, revtex4

Modern interconnects often have programmable processors in the network interface that can be utilized to offload communication processing from host CPU. In this paper, we explore different schemes to support collective operations at the network interface and propose a new collective protocol. With barrier as an initial case study, we have demontrated that much of the communication processing can be greatly simplified with this collective protocol. Accordingly, %with our proposed collective processing scheme, we have designed and implemented efficient and scalable NIC-based barrier operations over two high performance interconnects, Quadrics and Myrinet. Our evaluation shows that, over a Quadrics cluster of 8 nodes with ELan3 Network, the NIC-based barrier operation achieves a barrier latency of only 5.60$\mu$s. This result is a 2.48 factor of improvement over the Elanlib tree-based barrier operation. Over a Myrinet cluster of 8 nodes with LANai-XP NIC cards, a barrier latency of 14.20$\mu$s over 8 nodes is achieved. This is a 2.64 factor of improvement over the host-based barrier algorithm. Furthermore, an analytical model developed for the proposed scheme indicates that a NIC-based barrier operation on a 1024-node cluster can be performed with only 22.13$\mu$s latency over Quadrics and with 38.94$\mu$s latency over Myrinet. These results indicate the potential for developing high performance communication subsystems for next generation clusters., Comment: 8 pages, 8 figures

The I/O access patterns of many parallel applications consist of accesses to a large number of small, noncontiguous pieces of data. If an application's I/O needs are met by making many small, distinct I/O requests, however, the I/O performance degrades drastically. To avoid this problem, MPI-IO allows users to access noncontiguous data with a single I/O function call, unlike in Unix I/O. In this paper, we explain how critical this feature of MPI-IO is for high performance and how it enables implementations to perform optimizations. We first provide a classification of the different ways of expressing an application's I/O needs in MPI-IO--we classify them into four levels, called level~0 through level~3. We demonstrate that, for applications with noncontiguous access patterns, the I/O performance improves dramatically if users write their applications to make level-3 requests (noncontiguous, collective) rather than level-0 requests (Unix style). We then describe how our MPI-IO implementation, ROMIO, delivers high performance for noncontiguous requests. We explain in detail the two key optimizations ROMIO performs: data sieving for noncontiguous requests from one process and collective I/O for noncontiguous requests from multiple processes. We describe how we have implemented these optimizations portably on multiple machines and file systems, controlled their memory requirements, and also achieved high performance. We demonstrate the performance and portability with performance results for three applications--an astrophysics-application template (DIST3D), the NAS BTIO benchmark, and an unstructured code (UNSTRUC)--on five different parallel machines: HP Exemplar, IBM SP, Intel Paragon, NEC SX-4, and SGI Origin2000., Comment: 18 pages, 12 figures

Today's cluster computers suffer from slow I/O, which slows down I/O-intensive applications. We show that fast disk I/O can be achieved by operating a parallel file system over fast networks such as Myrinet or Gigabit Ethernet. In this paper, we demonstrate how the ParaStation3 communication system helps speed-up the performance of parallel I/O on clusters using the open source parallel virtual file system (PVFS) as testbed and production system. We will describe the set-up of PVFS on the Alpha-Linux-Cluster-Engine (ALiCE) located at Wuppertal University, Germany. Benchmarks on ALiCE achieve write-performances of up to 1 GB/s from a 32-processor compute-partition to a 32-processor PVFS I/O-partition, outperforming known benchmark results for PVFS on the same network by more than a factor of 2. Read-performance from buffer-cache reaches up to 2.2 GB/s. Our benchmarks are giant, I/O-intensive eigenmode problems from lattice quantum chromodynamics, demonstrating stability and performance of PVFS over Parastation in large-scale production runs., Comment: 22 pages, 10 figures

Use of Peer-to-Peer (P2P) service networks introduces a new communication paradigm because peers are both clients and servers and so each peer may provide/request services to/from other peers. Empirical studies of P2P networks have been undertaken and reveal useful characteristics. However there is to date little analytical work to describe P2P networks with respect to their communication paradigm and their interconnections. This paper provides an analytical formulation and optimisation of peer connection efficiency, in terms of minimising the fraction of wasted connection time. Peer connection efficiency is analysed for both a uni- and multi-connected peer. Given this fundamental optimisation, the paper optimises the number of connections that peers should make use of as a function of network load, in terms of minimising the total queue size that requests in the P2P network experience. The results of this paper provide a basis for engineering high performance P2P interconnection networks. The optimisations are useful for reducing bandwidth and power consumption, e.g. in the case of peers being mobile devices with a limited power supply. Also these results could be used to determine when a (virtual) circuit should be switched to support a connection., Comment: 9 pages

Multireader shared registers are basic objects used as communication medium in asynchronous concurrent computation. We propose a surprisingly simple and natural scheme to obtain several wait-free constructions of bounded 1-writer multireader registers from atomic 1-writer 1-reader registers, that is easier to prove correct than any previous construction. Our main construction is the first symmetric pure timestamp one that is optimal with respect to the worst-case local use of control bits; the other one is optimal with respect to global use of control bits; both are optimal in time., Comment: 11 pages LaTeX, 1 table, 2 pseudo-programs; previous version published in Proc 16th International Symposium on DIStributed Computing (DISC 2002), Lecture Notes in Computer Science, Vol 2508, Springer-Verlag, Berlin, 118-132. New version eliminates error in the protocol (merges a split scan operation that proved problematic) and defers the formal proof to a planned future I/O automaton version

We show that Naming-- the existence of distinct IDs known to all-- is a hidden but necessary assumption of Herlihy's universality result for Consensus. We then show in a very precise sense that Naming is harder than Consensus and bring to the surface some important differences existing between popular shared memory models., Comment: LaTeX, 15 pages, In: Distributed Computing Conference (DISC'00), Lecture Notes in Computer Science, Vol. 1914, Springer-Verlag, Berlin, 2000, 134--148

The Swiss Light Source (SLS) has in the order of 500 magnet power supplies (PS) installed, ranging from from 3 A/20 V four-quadrant PS to a 950 A/1000 V two-quadrant 3 Hz PS. All magnet PS have a local digital controller for a digital regulation loop and a 5 MHz optical point-to-point link to the VME level. The PS controller is running a pulse width/pulse repetition regulation scheme, optional with multiple slave regulation loops. Many internal regulation parameters and controller diagnostics are readable by the control system. Industry Pack modules with standard VME carrier cards are used as VME hardware interface with the high control density of eight links per VME card. The low level EPICS interface is identical for all 500 magnet PS, including insertion devices. The digital PS have proven to be very stable and reliable during commissioning of the light source. All specifications were met for all PS. The advanced diagnostic for the magnet PS turned out to be very useful not only for the diagnostic of the PS but also to identify problems on the magnets., Comment: 3 pages, 4 graphics, ICALEPCS 2001 paper (Poster)

Shared registers are basic objects used as communication mediums in asynchronous concurrent computation. A concurrent timestamp system is a higher typed communication object, and has been shown to be a powerful tool to solve many concurrency control problems. It has turned out to be possible to construct such higher typed objects from primitive lower typed ones. The next step is to find efficient constructions. We propose a very efficient wait-free construction of bounded concurrent timestamp systems from 1-writer multireader registers. This finalizes, corrects, and extends, a preliminary bounded multiwriter construction proposed by the second author in 1986. That work partially initiated the current interest in wait-free concurrent objects, and introduced a notion of discrete vector clocks in distributed algorithms., Comment: LaTeX source, 35 pages; To apper in: J. Assoc. Comp. Mach

Many scientific applications are I/O intensive and generate or access large data sets, spanning hundreds or thousands of "files." Management, storage, efficient access, and analysis of this data present an extremely challenging task. We have developed a software system, called Scientific Data Manager (SDM), that uses a combination of parallel file I/O and database support for high-performance scientific data management. SDM provides a high-level API to the user and internally, uses a parallel file system to store real data and a database to store application-related metadata. In this paper, we describe how we designed and implemented SDM to support irregular applications. SDM can efficiently handle the reading and writing of data in an irregular mesh as well as the distribution of index values. We describe the SDM user interface and how we implemented it to achieve high performance. SDM makes extensive use of MPI-IO's noncontiguous collective I/O functions. SDM also uses the concept of a history file to optimize the cost of the index distribution using the metadata stored in the database. We present performance results with two irregular applications, a CFD code called FUN3D and a Rayleigh-Taylor instability code, on the SGI Origin2000 at Argonne National Laboratory., Comment: 7 pages + title page