Parallel Processing Letters

We are pursuing the FUCE architecture project at Kyushu University. FUCE means FUsion of Communication and Execution. The main objective of our research is, as the name shows, to develop a new architecture that truly fuses communication and computation. The FUCE project develops a new on-chip-multi-processor and kernel software on it. We name the processor FUCE processor, and the kernel software as CEFOS (Communication and Execution Fusion OS).

The FUCE processor is designed as a network node processor to perform mainly switching/transmitting of messages/transaction and handling its contents. FUCE processor architecture is designed as a multiprocessor-on-chip to support the fine-grain multi-threading.

The kernel software CEFOS is also developed on the concept of multithreading. User and system processes are constructed as a set of threads, which are executed concurrently according to thread dependences.

We present our experiences in developping and tuning the performance at the user level, of (in core) parallel sorting on homogeneous and non homogeneous clusters with the use of the two available BSP (Bulk Synchronous Parallel model) libraries: BSPLib from Oxford university (UK) and PUB7 from the university of Paderborn (Germany). The paper is mainly about the communication performances of these two libraries and, in more general terms, it compares and summarizes the programming facilities and differences between them.

Beowulf class clusters are gaining more and more interest as low cost parallel architectures. They deliver reasonable performance at a very reasonable cost, compared to classical MPP machines. Parallel applications are usually developed on clusters using MPI/PVM message passing or HPF programming environments. Here we discuss new implementation strategies to support structured parallel programming environments for clusters based on skeletons. The adoption of structured parallel programming models greatly reduces the time spent in developing new parallel applications on clusters. The adoption of our implementation techniques based on macro data flow allows very efficient parallel applications to be developed on clusters. We discuss experiments that demonstrate the full feasibility of the approach.

Smart cards are highly successful thanks to their unique combination of mobility and security. Based upon a single-chip microcontroller with volatile and non-volatile memories, a smart card implementes a small computer system that is very portable (credit card size), easy to use, and extremely resistant against external attacks.

However, today's smart cards use proprietary protocols, application schemes, and development tools. This is due to the limitations of current technology, and it leads to situation of "splendid isolation" where smart cards are not being regarded as an integral part of the overall IT architecture.

In this paper, we describe recent research towards "next generation" smart cards. It combines an advanced programming language (Java), novel hardware architectures that provide the required "MIPS budget" (RISC 32 bit), as well as an implementation of key Internet protocols (IP, HTTP) on smart cards.

As a result, we show how smart cards can be seamlessly integrated within a distributed computing environment.

In this article, we introduce a new logical clock, the barrier-lock clock, whose conception is based on the lazy release consistency memory model (LRC) supported by several distributed shared memory (DSM) systems. Since in the LRC, the propagation of shared memory updates performed by the processes of a parallel application is induced by lock and barrier operations, our logical clock has been modeled on those operations. Each barrier-lock times-tamp encodes the synchronization operation with which it is associated. Its size is not dependent on the number of processes of the system, as the traditional logical vector clocks, but it is proportional to the number of locks. The barrier-lock time characterizes the causality of shared memory updates performed by processes of a parallel application running on a LRC-based DSM system. A formal proof and experimental tests have confirmed such property.

The gradual evolution of language features and approaches used for the programming of distributed memory machines underwent substantial advances in the 1990s. One of the most promising and widely praised approaches was based on data parallelism and resulted in High Performance Fortran. This paper reports on an experiment using that approach based on a commercial distributed memory machine, available compilers and simple test programs. The results are disappointing and not encouraging. The variety of components involved and the lack of detailed knowledge available for the compilers compound the difficulties of obtaining results and doing comparisons. The results show great variation and question the premise that communication is the decisive factor in performance determination. The results are also a contribution towards the difficult tasks of predicating performance on a distributed memory computer.

It is now well recognized that consensus is a fundamental problem one has to solve to implement reliable applications on top of unreliable asynchronous distributed systems prone to failures. It has been shown that this problem cannot be solved if the underlying asynchronous system does not satisfy additional assumptions. This paper presents a new consensus protocol based on a leader oracle (denoted Ω in the litterature). Although this protocol uses asynchronous rounds, it is not based on the rotating coordinator paradigm. As a consequence, it does not suffer from drawbacks inherent to ♢S-based consensus protocols that explicity use this paradigm. As Ω and ♢S are equivalent, the proposed protocol does not require assumptions stronger or weaker than the ones abstracted in ♢S. Hence, it also requires f < n/2 (where n is the number of processes and f an upper bound on the number of processes that may crash). From a design point of view, the proposed protocol is surprisingly simple. From an efficiency point of view, it allows the processes to agree in a single round when the oracle provides the processes with the same leader (a common case in practice). It is also shown that the time and message costs of the protocol can be reduced when f < n/3. Moreover, when, in addition to the leader oracle, the system is equipped with a random oracle, the proposed protocol can be extended to provide a hybrid consensus protocol at no additional message cost.

In this paper we present a performance model for a constant service time, globally synchronized multistage interconnection network that is an improvement on earlier work in this field. The events at the network input are assumed to have a geometric distribution in time. As the events are combined within the network, it can happen that two events arrive simultaneously at one of the network server elements, called a double arrival rate stream (DAR) server. Analytical methods are described to derive the response time and inter-departure time distribution of the double arrival rate constant service time server, which has a queuing property (DAR/D/1). Due to the queuing effect of the servers in the first stage of the network, their outputs show a "distorted" geometric distribution, which is known to introduce analytical difficulties in the performance evaluation of the subsequent stages. A method is presented to derive the response time of servers in the second stage, when the network has a uniform workload distribution. It is shown that the knowledge of the response times of the first and second stage of the network is sufficient to predict the total response time of a large network with an accuracy better than 3%, even under a heavy workload.

Given a text and a pattern, the problem of pattern matching consists of determining all the positions of the text where the pattern occurs. When the text and the pattern are matrices, the matching is termed bidimensional. There are variations of this problem where we allow the matching using a somehow modified pattern. A modification that we will allow is that the pattern can be scaled. We propose a new parallel algorithm for this problem, under the CGM (Coarse Grained Multicomputer) model. This algorithm requires linear local computing time in the input, linear memory and uses only one communication round, during which at most a linear amount of data is exchanged. To be the best of our knowledge, there are no known parallel algorithms for the bidimensional pattern matching problem with scaling in the literature. This proposed algorithm was implemented in C, using the PVM interface and was executed on a Parsytec PowerXplorer parallel machine. The experimental results obtained were very promising and showed significant speedups.

Net-Console is an integrated program development environment that can be used as a front-end for High Performance Computing (HPC) sites. It consist of an MPI-aware editor, an execution console, a debugger, monitoring tools and an account and file manager. Using Net-console the user is able to edit, execute, debug and evaluate the performance of parallel programs from anywhere in the Internet. The user interface is done through a normal Java-enabled browser. Net-console can also support processing through wireless and lightweight devices with the use of mobile agent technologies. The tools included in Net-console and their functionality, the languages used and the overall structure of the project are presented in this paper.

Symbolic allocation and dynamic scheduling of tasks on a distributed memory machine for coarse-grained applications represented by parameterized task graphs (PTG) are presented in this paper. A PTG is a new computation model for symbolically representing directed acyclic task graphs (DAGs). The size of a PTG is independent of the problem size and its parameters can be instantiated at run time. Parameter independent optimization is important for exploiting non-static parallelism in scientific computing programs with varying problem sizes. Previous DAG scheduling algorithms are not able to handle such cases. We present and study a symbolic scheduling algorithm called SLC (Symbolic Linear Clustering) which derives task clusters from a PTG using affine piecewise mapping functions and then evenly assigns clusters to processors. Thus a complete automatic parallelization method is presented.

Designing multi-processor systems that deliver a reasonable price-performance ratio using off-the-shelf processor and compiler technologies is a major challenge. For an important class of applications, it is critical to explore fine-grain parallelism to achieve reasonable performance. In such parallel systems it is essential to efficiently manage communication latencies, bandwidth, and synchronization overheads. In this paper we study load balancing strategies for the runtime system of a multi-threaded system. EARTH (Efficient Architecture for Running Threads) is a multi-threaded programming and execution model that supports fine-grain, non-preemptive, threads in a distributed memory environment. We describe the design and implementation of a set of dynamic load balancing algorithms, and study their performance in divide-and-conquer, regular, and irregular applications. Our experimental study on the distributed memory multi-processor IBP SP-2 indicate that a randomized load balancer perform as well as, and often better than, history based load balancers.