To design a Java processor with traditional modern processor architecture, the instruction level parallelism (ILP) is not readily exploitable due to stack operands dependencies. This paper presents a dataflow-based instruction tagging scheme. With instruction tagging, the independent bytecode instruction groups with stack dependences are identified. The different bytecode instruction group can be executed in parallel because there are no stack dependences among them. With the instruction tagging scheme, we propose a tag-based multi-issue semi-in-order (TMSI) Java processor. The processor takes advantage of instruction-tagging and stack-folding to generate the tagged register-based instructions. When the tagged instructions are ready, they are bundled out-of-order depending on data availability to form VLIW-like instruction words and issued in-order. To achieve high performance, a VLIW engine is employed. We have conducted some experiments in our TMSI simulation environment using SPECjvm98 and Linpack workload. The results indicate that the proposed processor has good performance gain.

Distributed Shared Memory (DSM) is a highly desirable programming model for cluster based computing. Even though a number of software DSMs have been developed with their performance evaluated, few of them have a theoretical performance model. In this paper, we propose and analyze the performance model of the software DSM of SilkRoad,, a multithreaded runtime system for cluster computing. SilkRoad is built on the Cilk system with an extended memory consistency model which we call RC/sub dag/ consistency: Extending Cilk's theoretical performance model, we show that with the RC/sub dag/ consistent DSM, the expected execution.time T/sub P/ of a partially strict multithreaded computation on P processors is O((T/sub 1/(Z, L) + N)/P + /spl mu/HT/sub /spl infin//), where T/sub 1/(Z, L) is the total work of computation, T/sub /spl infin// is the critical path, N is the number of lock acquisitions, /spl mu/ is the service time of a cache miss, and H is the height of memory: Finally, we present experimental evidence that verify the performance model.

A parallel programming paradigm dictates the way in which an application is to be expressed. It also restricts the algorithms that may be used in the application. Unfortunately, runtime systems for parallel computing often impose a particular programming paradigm. For a wider choice of algorithms, it is desirable to support more than one paradigm. In this paper we consider SilkRoad II, a variant of the Cilk runtime system for cluster computing. What is unique about SilkRoad II is its memory model which supports multiple paradigms with the underlying software distributed shared memory. The RC-dag memory consistency model of SilkRoad II is introduced. Our experimental results show that the stronger RC-dag can achieve performance comparable to LC of Cilk while supporting a bigger set of paradigms with rather good performance.

Constructing multithreaded parallel systems with software distributed shared memory (DSM) is an attractive trend in cluster computing. Distributed Cilk (Cilk 5.1) is a multithreaded runtime system for SMP clusters with support for the divide-and-conquer programming paradigm. However, it lacks support for user-level shared memory. We describe SilkRoad, an extension of Distributed Cilk which implements the lazy release consistency (LRC) memory model. In the SilkRoad runtime system, system control information is kept consistent by means of a backing store, just as it is in the original Distributed Cilk, while the user's cluster wide shared data is kept consistent by LRC. LRC enables SilkRoad programmers to define and use shared variables between the threads running on different nodes in a cluster This greatly enlarges the scope of supported programming paradigms in Cilk. Besides testing its performance, we also compared SilkRoad with TreadMarks, an LRC software DSM system for clusters with no support of multithreading. The results show that with the hybrid memory model of dag-consistency and LRC, multithreaded SilkRoad programs written in a divide-and-conquer fashion with good data locality can achieve comparable performance with the corresponding multiple-process TreadMarks programs.

A truly random sequence of numbers has an asymptotically flat Walsh power spectrum. This fact is used to devise a new test for the randomness of the output of random number generators. Because it takes little computing time to obtain the Walsh power spectrum of even very long sequences, generators with large periods can be tested. Some computed examples are shown.

Function approximation by a finite Walsh series is considered. There are two methods for selecting the terms of a series. The process of threshold sampling gives a least-square error approximation, but no error analysis technique is available. However, error analysis is possible if terms are selected according to degrees and subdegrees. It is shown that truncation is equivalent to dropping all terms with degrees greater than some amount. The error caused is a weighted integral of the first derivative, and an upper bound on the expression can be derived. It is also shown that a truncated Walsh series corresponds to a simple function table. Data compression is equivalent to dropping terms with large enough subdegrees, with an estimable error. After a Walsh series has been selected, it is possible to modify the coefficients using Lawson's algorithm and reduce the maximum error.

When reading the above paper1, the unwary person might easily come to the conclusion that "most carries are short." Actually, such a statement needs to be qualified. In fact, if a computer engineer designs an adder on this basis, he would probably find that the average add time is not as short as the theoretical analysis would lead him to expect. This is because Briley's analysis, and that of his predecessors Burks, Goldstine, and von Neumann [1], are both dependenent on the assumption that the numbers being added are evenly distributed among 2n possible bit combinations. In actual computation, most of the integers tend to have small magnitudes. Thus, a negative integer, if expressed in complement form, tends to have a long string of leading ones. When two such numbers are added, or when one of these is added to a positive integer giving a positive sum, a long string of carries would be generated. This means that in real computing situations the average carry might be much longer than Briley's analysis would indicate.

An expression for evaluating the Walsh power spectra of random signals with very short time correlations is given.

Although the conversion from octal to binary is a trivially simple process, it is still somewhat trying to have to mentally perform the conversion when reading a long list of octal numbers. The problem becomes especially annoying when one is examining the memory dump of the word contents of a machine which has a byte size not divisible by three (e.g., PDP-11). In such cases some of the octal digits contain portions of neighboring bytes. For example, in the octal representation of a 16-bit word made up of two 8-bit bytes the third digit from the right contains two bits of the right-hand byte and one bit of the left-hand byte. Unless one is very experienced in mental conversions it is very difficult to know the contents of the bytes without actually writin, down the binary representation.

Concepts of group theory are used to explain the difference between two major fast Fourier transform (FFT) algorithms and the relation between FFT and fast Walsh transforms.

Many applications of Walsh functions employ Walsh series expansions. To obtain the advantage of data compression many of the Walsh coefficients must be negligible. It is thus desirable to have a scheme by which their magnitudes can be estimated with little computation. We found that the Walsh transform Fi of a function that can be differentiated by an arbitrary number of times is expressible as a weighted average of one of its derivatives. The mean and maximum of the weighting function is readily expressed in terms of i, from which we derived two upper bounds on Fi depending only on i and the maximum or mean magnitude of the derivative. As the bounds decrease rapidly with increasing degree and rank, Walsh transforms with high degree and rank are negligible. We also proved that discrete Walsh transforms calculated using sampled values obey the same bounds. While bounds can also be found for transforms of functions that can be differentiated by only a finite number of times, they tend to be larger and less dependent on rank. As most autocorrelation functions have singularities in second derivative, bounds on Walsh power spectra depend only on degree. Computed examples show that the behavior of Walsh spectra closely follow that of their upper bounds.