bluuebunny/crossref_metadata_2025 huggingface dataset:
Scheduling multiple queries on a parallel machine
Authors: Wolf Joel L. , Turek John , Chen Ming-Syan , Yu Philip S.
Published: January 2007

There has been a good deal of progress made recently towards the efficient parallelization of individual phases of single queries in multiprocessor database systems. In this paper we devise and evaluate a number of scheduling algorithms designed to handle multiple parallel queries. One of these algorithms emerges as a clear winner. This algorithm is hierarchical in nature: In the first phase, a good quality precedence-based schedule is created for each individual query and each possible number of processors. This component employs dynamic programming. In the second phase, the results of the first phase are used to create an overall schedule of the full set of queries. This component is based on previously published work on nonprecedence-based malleable scheduling. Even though the problem we are considering is NP-hard in the strong sense, the multiple query schedules generated by our hierarchical algorithm are seen experimentally to achieve results which are close to optimal.
Asymptotic performance of a buffer model in a data sharing environment
Authors: Bittan Avi , Kogan Yaakov , Yu Philip S.
Published: January 2007

The performance of a transaction processing system is very sensitive to the buffer hit probability. In a data sharing environment where multiple computing nodes are coupled together with direct access to shared data on disks, buffer coherency needs to be maintained such that if a data granule is updated by a node, the old copies of this granule present in the buffer of other nodes must be invalidated. The buffer invalidation phenomenon reduces the buffer hit probability in a multi-node environment. After the buffer reaches a certain size, the buffer hit probability will remain constant regardless of further increase in buffer size due to the buffer invalidation effect. This puts an upper limit on the achievable buffer hit probability. Thus the selection of appropriate buffer size is one of the critical issues in a data sharing environment. In this paper, we develop an asymptotic analysis of the Markov model for a buffer in the data sharing environment. Important relations between buffer size, number of nodes, write-probability and the size of the database to the buffer hit probability had been found in all range of system parameters. A simple expression is obtained for the maximum achievable buffer hit probability and also for the maximum usable buffer size. Various properties of the maximum achievable buffer hit probability and usable buffer size are derived for a skewed access workload. The accuracy of the asymptotic method is validated by numerous case studies.
Phased-mission system analysis using Boolean algebraic methods
Authors: Somani Arun K. , Trivedi Kishor S.
Published: January 2007

Most reliability analysis techniques and tools assume that a system is used for a mission consisting of a single phase. However, multiple phases are natural in many missions. The failure rates of components, system configuration, and success criteria may vary from phase to phase. In addition, the duration of a phase may be deterministic or random. Recently, several researchers have addressed the problem of reliability analysis of such systems using a variety of methods. We describe a new technique for phased-mission system reliability analysis based on Boolean algebraic methods. Our technique is computationally efficient and is applicable to a large class of systems for which the failure criterion in each phase can be expressed as a fault tree (or an equivalent representation). Our technique avoids state space explosion that commonly plague Markov chain-based analysis. We develop a phase algebra to account for the effects of variable configurations and success criteria from phase to phase. Our technique yields exact (as opposed to approximate) results. We demonstrate the use of our technique by means of an example and present numerical results to show the effects of mission phases on the system reliability.
A quantitative analysis of cache policies for scalable network file systems
Authors: Dahlin Michael D. , Mather Clifford J. , Wang Randolph Y. , Anderson Thomas E. , Patterson David A.
Published: January 2007

Current network file system protocols rely heavily on a central server to coordinate file activity among client workstations. This central server can become a bottleneck that limits scalability for environments with large numbers of clients. In central server systems such as NFS and AFS, all client writes, cache misses, and coherence messages are handled by the server. To keep up with this workload, expensive server machines are needed, configured with high-performance CPUs, memory systems, and I/O channels. Since the server stores all data, it must be physically capable of connecting to many disks. This reliance on a central server also makes current systems inappropriate for wide area network use where the network bandwidth to the server may be limited.

In this paper, we investigate the quantitative performance effect of moving as many of the server responsibilities as possible to client workstations to reduce the need for high-performance server machines. We have devised a cache protocol in which all data reside on clients and all data transfers proceed directly from client to client. The server is used only to coordinate these data transfers. This protocol is being incorporated as part of our experimental file system, xFS. We present results from a trace-driven simulation study of the protocol using traces from a 237 client NFS installation. We find that the xFS protocol reduces server load by more than a factor of six compared to AFS without significantly affecting response time or file availability.
An approach to scalability study of shared memory parallel systems
Authors: Sivasubramaniam Anand , Singla Aman , Ramachandran Umakishore , Venkateswaran H.
Published: January 2007

The overheads in a parallel system that limit its scalability need to be identified and separated in order to enable parallel algorithm design and the development of parallel machines. Such overheads may be broadly classified into two components. The first one is intrinsic to the algorithm and arises due to factors such as the work-imbalance and the serial fraction. The second one is due to the interaction between the algorithm and the architecture and arises due to latency and contention in the network. A top-down approach to scalability study of shared memory parallel systems is proposed in this research. We define the notion of
overhead functions
associated with the different algorithmic and architectural characteristics to
quantify
the scalability of parallel systems; we isolate the algorithmic overhead and the overheads due to network latency and contention from the overall execution time of an application; we design and implement an execution-driven simulation platform that incorporates these methods for quantifying the overhead functions; and we use this simulator to study the scalability characteristics of five applications on shared memory platforms with different communication topologies.
A comparison of two model-based performance-prediction techniques for message-passing parallel programs
Authors: Mehra Pankaj , Schulbach Catherine H. , Yan Jerry C.
Published: January 2007

This paper describes our experience in modeling two significant parallel applications: ARC2D, a 2-dimensional Euler solver; and, Xtrid, a tridiagonal linear solver. Both of these models were expressed in BDL (Behavior Description language) and simulated on an iPSC/860 Hypercube modeled using Axe (Abstract eXecution Environment). BDL models consist of abstract communicating objects: blocks of sequential code are modeled by single RUN statements; all communication operations in the original code are mirrored by corresponding BDL operations in the model. Our ARC2D model was built by first profiling the program to locate the significant loops and then timing the basic blocks within those loops. Simulated completion times were (except in one case) within 8% of measured execution times. Lengthy simulations were necessary for predicting the performance of large-scale runs. For Xtrid, only the loops surrounding communications were modeled; other loops were absorbed into large sequential blocks whose complexity was estimated using statistical regression. This approach yielded a much smaller model whose computation and communication complexities were clearly manifest. Analysis of complexity allowed rapid prediction of large-scale performance without lengthy simulations! Analytically predicted speed-ups were within 7% of those predicted by simulation. Simulated completion times were within 5% of measured execution times. The second approach provides a more effective methodology for simulation-based performance-tuning.
A multi-level solution algorithm for steady-state Markov chains
Authors: Horton Graham , Leutenegger Scott T.
Published: January 2007

A new iterative algorithm, the
multi-level
algorithm, for the numerical solution of steady state Markov chains is presented. The method utilizes a set of recursively coarsened representations of the original system to achieve accelerated convergence. It is motivated by multigrid methods, which are widely used for fast solution of partial differential equations. Initial results of numerical experiments are reported, showing significant reductions in computation time, often an order of magnitude or more, relative to the Gauss-Seidel and optimal SOR algorithms for a variety of test problems. It is shown how the well-known iterative aggregation-disaggregation algorithm of Takahashi can be interpreted as a special case of the new method.
Providing end-to-end statistical performance guarantees with bounding interval dependent stochastic models
Authors: Zhang Hui , Knightly Edward W.
Published: January 2007

This paper demonstrates a new, efficient, and general approach for providing end-to-end performance guarantees in integrated services networks. This is achieved by modeling a traffic source with a family of bounding interval-dependent (BIND) random variables and by using a rate-controlled service discipline inside the network. The traffic model stochastically bounds the number of bits sent over time intervals of different length. The model captures different source behavior over different time scales by making the bounding distribution an explicit function of the interval length. The service discipline, RCSP, has the priority queueing mechanisms necessary to provide performance guarantees in integrated services networks. In addition, RCSP provides the means for efficiently extending the results from a single switch to a network of arbitrary topology. These techniques are derived analytically and then demonstrated with numerical examples.
Scheduling algorithms for modern disk drives
Authors: Worthington Bruce L. , Ganger Gregory R. , Patt Yale N.
Published: January 2007

Disk subsystem performance can be dramatically improved by dynamically ordering, or
scheduling
, pending requests. Via strongly validated simulation, we examine the impact of complex logical-to-physical mappings and large prefetching caches on scheduling effectiveness. Using both synthetic workloads and traces captured from six different user environments, we arrive at three main conclusions: (1) Incorporating complex mapping information into the scheduler provides only a marginal (less than 2%) decrease in response times for seek-reducing algorithms. (2) Algorithms which effectively utilize prefetching disk caches provide significant performance improvements for workloads with read sequentiality. The cyclical scan algorithm (C-LOOK), which always schedules requests in ascending logical order, achieves the highest performance among seek-reducing algorithms for such workloads. (3) Algorithms that reduce overall positioning delays produce the highest performance provided that they recognize and exploit a prefetching cache.
An interactive diagnostic/debugging subsystem for bit-slice processors
Authors: Burkowski F. J.
Published: January 2007

This paper discusses the design and implementation of a debugging/diagnostic subsystem for a bit-slice processor. The subsystem uses serial shadow registers under the control of a single chip microcomputer both to observe and to control processor behavior. Serial lines link the microcomputer to a diagnostic host which provides the user with a comprehensive set of interactive diagnostic commands. Using these commands, the user is able to load the writable control store, verify its contents, load mapping facilities, set breakpoints and examine registers during single-stepping sequences. The subsystem can considerably speed up the firmware development process and when incorporated into the design as a permanent feature, it provides a very low-cost facility for register-level diagnostics during the life of the system. Portability of the diagnostic subsystem across a number of processors is also possible and is conducive to the efficient management of machine diagnosis in the field.
Verification of microprogrammed computer architectures in the S*-system: a case study
Authors: Damm W. , Dohmen G.
Published: January 2007

We apply the verification methodology underlying the S*-System[12], [13] to the verification of a hierarchically structured design [16] of an emulation of the instruction-set of a commercially available computer on a commercially available micro-architecture. Based on this case-study, we discuss some aspects of the relation between verification and generation of microcode.
HPS, a new microarchitecture: rationale and introduction
Authors: Patt Y. N. , Hwu W. M. , Shebanow M.
Published: January 2007

HPS (High Performance Substrate) is a new microarchitecture targeted for implementing very high performance computing engines. Our model of execution is a restriction on fine granularity data flow. This paper introduces the model, provides the rationale for its selection, and describes the data path and flow of instructions through the microengine.
The design of an interactive compiler for optimizing microprograms
Authors: Vegdahl S. R.
Published: January 2007

Microprogramming has traditionally been done in assembly language because of the perceived need for fast execution; compiler technology does not yet exist for discovering and performing many of the clever tricks of an experienced microprogrammer. Unfortunately, programming at the machine-instruction level is both tedious and error-prone. A possible compromise between these two approaches is that of an interactive compiler, where the programmer guides the crafting of critical data structures and sections of code, while the compiler ensures that the resulting code has the same semantics as the original program, generates code where speed is not critical, and performs bookkeeping tasks. We are in the process of implementing a prototype of such a system. This paper describes the system being developed and discusses some of the key design issues.
Target-independent high-level microprogramming
Authors: Hopkins W. C. , Horton M. J. , Arnold C. S.
Published: January 2007

We describe a system which allows high-level microprogramming without requiring programmer knowledge of the target architecture, depending instead on retargetable microcode generation and optimization. In the ideal system the code generation, microcode compaction, encoding and simulation are driven by a single description of the target microarchitecture. An initial implementation, which is now working for a real microprogrammable processor, demonstrates the feasibility of the key technologies.
STEP development tools: METASTEP language system
Authors: Wilburn D. L. , Schleimer S.
Published: January 2007

STEP Development Tools (SDT) is a general-purpose microprogram development system. The METASTEP language system is composed of four tools of the SDT needed to write microprograms: a Definition Processor, a Retargetable Assembler, a Retargetable Cross-Assembler, and a Relocatable Linker.

These tools are of commercial quality, providing complete languages, quality diagnostics, full interface to other support tools, and high performance. The language system supports microcode debug by providing complete run-time information and by interacting directly with other debug tools provided in SDT.
Geometric data of cross-sections of beams
Authors: Besier Holger
Published: January 2007

This paper describes a program which calculates the geometrical characteristic values of cross-sections of beams with complex shapes (bars or thin-walled profiles with any number of holes in the profiles).

After a short introduction describing the calculations involved for moments of area, we will introduce the capabilities of every component of this program and we will make a survey of the whole system via flow chart.

At the end of the paper we will summarize the main features of the program and mention some possible extensions.
LiSEB
Authors: Bottoni P. , Mariotto M. , Mussio P.
Published: January 2007

The paper discusses the design and implementation of LiSEB, a class-based language built on top of APL2 to respond to challenges posed by modelling living systems from a medical point of view. LiSEB capitalises on several features of APL and on some lessons learned from its history. Living systems are modelled as open systems: environments in which concurrent mobile autonomous agents interact. Modelling of these properties required extensions of traditional object-oriented paradigms and of their previous translations under APL: a) every object performs a sequence of actions dynamically modified to adapt to circumstances; b) a new policy of message management is introduced uniformly encompassing broadcast and directly addressed communication. An example of a simulation using LiSEB illustrates these concepts.
A new graphical user interface proposal for APL
Authors: Bowman Dick
Published: January 2007

In the past APL had two significant advantages over many other problem-solving computational tools. The first of these was that the language elements of APL have a consistency and breadth that remains unchallenged, at least for the tasks for which they were designed. The other historic advantage of APL, that it provided an interactive problem-solving environment, has long since been eroded. Indeed, we have seen a transformation of some programming languages into programming environments.

The purpose of this paper is to explore some possible ways in which the face that APL presents to those who program with it could usefully be enhanced.
Programming in J/Windows
Authors: Burke Chris
Published: January 2007

J has been available as shareware for the last four years. The core language has been largely complete from outset, but it is only comparatively recently that the implementation (at least for the PC) has included features needed for serious application development.

The most significant change was the introduction of Windows support in release 6, which for the first time allowed full screen applications to be written in J. Following the release of 6.2, which included many additions to the Windows support and a much better session manager, I started using the Windows version of J in small applications, for which I would normally have used APL. Since then I have switched over to using J for almost all development, except for client work where APL is specifically required. I believe that J is already comparable to commercial APL's for application development and will soon be superior.

In this paper, I will describe programming the J/Windows interface, and discuss some practical considerations in using it.
APL and economic education
Authors: Buzin Andrew Yu.
Published: January 2007

The experience of teaching economics with computers is discussed. Using APL and GRAN provides for very interactive graphical interpretation of classical economic models. The static Leontieff's model, the business cycle model and the macro equilibrium model are considered as examples.

Two approaches to the teaching of economics with computers are proposed. The first is the simultaneous teaching of APL and economics. APL permits the very fast and concise coding of the models (the comparison is made with Kuboniwa's book) and their interactive exploration. The second approach represents a dialog between the computer and the students as well as the animation of illustrations of classical economic courses.
A risk management prototype using object-oriented APL
Authors: Gfeller Martin
Published: January 2007

After a quick introduction to Financial Risk Management, I show that Object-Oriented Technology (OOT) fits well with the demands of Risk Management. I then outline the analysis, design, and implementation of a prototype system for Risk Management using both OOT and APL. I describe a Dyalog APL implementation of OOT, and conclude by wondering whether APL is really suitable for OOT.
APL for statistical research of atmospheric flows during the dust storm
Authors: Mukanova Aibarsha A.
Published: January 2007

The existence of the Aral Sea depends almost completely on the waters of the Amudarya and Syrdarya rivers, so that a considerable decrease in the flow in the drainage-basin of these rivers results in a lower sea level. As a result huge areas of sea bottom are now revealed, mainly on the eastern sea coast. A significant part of this area is comprised of deposits of a loose mechanical composition, mainly from dust, which is exposed to intensive weathering.

Although dust storms in the Aral Sea zone occurred before, the appearance of a new powerful source for salt and dust transport evokes well founded anxiety. This source appeared in a satellite photo in 1975, and the decoded data showed the transportation of salt-dust masses reaching the south and west sea coast. Later investigations show that this source area has a tendency to increase with the formation of a huge zone of moving dust. There is also the problem of the desertification of the Aral east coast.

In the world the study of dust aerosol qualities has received great attention, because the deserts which occupy more than 30% of the land area are the main source of dust aerosol. Special attention is given to experimental and theoretical investigations of desert aerosol transport problems for the quantitative description of the wind driven transfer of dust from source to precipitation area.
The future of speech and audio in the interface
Authors: Arons Barry , Mynatt Elizabeth
Published: January 2007

Speech and audio are rapidly becoming integrated into our daily computing environments. While the traditional "terminal beep" still exists, it is being supplemented with a variety of other speech and non-speech sounds, as well as speech input to control applications and user interfaces. This workshop explored current and future applications, research areas, and interaction techniques that use audio in the user interface. The emphasis of the meeting was on a user interface, or "CHI perspective", of using speech and sound in interactive contexts where the audio channel can be exploited for the user's benefit.
A distributed memory LAPSE
Authors: Dickens Phillip M. , Heidelberger Philip , Nicol David M.
Published: January 2007

This paper describes a tool, LAPSE (Large Application Parallel Simulation Environment), that allows one to use a small number of parallel processors to simulate the behavior of a message-passing code running on a large number of processors, for the purposes of scalability studies and performance tuning. LAPSE is implemented on the Intel Paragon, and has achieved small slowdowns (relative to native code) and high speed-ups on large problems.
Discrete-event simulation and the event horizon
Authors: Steinman Jeff S.
Published: January 2007

The event horizon is a very important concept that is useful for both parallel and sequential discrete-event simulations. By exploiting the event horizon, parallel simulations can process events in a manner that is risk-free (i.e., no antimessages) in adaptable “breathing” time cycles with variable time widths. Additionally, exploiting the event horizon can greatly reduce the event list management overhead that is common to virtually all discrete-event simulations.

This paper develops an analytic model describing the event horizon from first principles using equilibrium considerations and the hold model (where each event, when consumed, generates a single new event with future-time statistics described by a known probability function). Exponential and Beta-density functions are used to verify the mathematics presented in this paper.
pGVT: an algorithm for accurate GVT estimation
Authors: D'Souza Loy M. , Fan Xianzhi , Wilsey Philip A.
Published: January 2007

The time warp mechanism uses memory space to save event and state information for rollback processing. As the simulation advances in time, old state and event information can be discarded and the memory space reclaimed. This reclamation process is called fossil collection and is guided by a global time value called Global Virtual Time (GVT). That is, GVT represents the greatest minimum time of the fully committed events (the time before which no rollback will occur). GVT is then used to establish a boundary for fossil collection. This paper presents a new algorithm for GVT estimation called pGVT. pGVT was designed to support accurate estimates of the actual GVT value and it operates in an environment where the communication subsystem does not support FIFO message delivery and where message delivery failure may occur. We show that pGVT correctly estimates GVT values and present some performance comparisons with other GVT algorithms.
Parallel simulation of a high speed LAN
Authors: Rönngren R. , Rajaei H. , Popescu A. , Liljenstam M. , Ismailov Y. , Ayani R.
Published: January 2007

Simulation of communication networks is often time consuming. Parallel simulation may be used to reduce the execution time of such a simulator. However, efficient modeling and simulation of such complex applications is not a trivial task. In this paper, we discuss the results of simulating a multigigabit/s network using both an optimistic and a conservative scheme. Our experimental result on a shared memory multiprocessor indicates that the conservative approach is superior to the optimistic one for this application.
Evaluating the use of pre-simulation in VLSI circuit partitioning
Authors: Chamberlain Roger D. , Henderson Cheryl D.
Published: January 2007

One of the significant difficulties in partitioning logic circuits for distributed simulation is the lack of a priori knowledge concerning the evaluation frequency of individual circuit elements. A number of researchers have resorted to pre-simulation to estimate these evaluation frequencies. In this paper we empirically investigate the wisdom of relying on pre-simulation results, and evaluate the degree to which early evaluation frequencies predict later evaluation frequencies. The results show that, for simulations that use random input vectors, pre-simulation has clear merit in predicting circuit element evaluation frequency. This supports the use of pre-simulation as an input to circuit partitioning algorithms.
Cost/performance of a parallel computer simulator
Authors: Falsafi Babak , Wood David A.
Published: January 2007

This paper examines the cost/performance of simulating a hypothetical
target
parallel computer using a commercial
host
parallel computer. We address the question of whether parallel simulation is simply faster than sequential simulation, or if it is also more cost-effective. To answer this, we develop a performance model of the Wisconsin Wind Tunnel (WWT), a system that simulates cache-coherent shared-memory machines on a message-passing Thinking Machines CM-5. The performance model uses Kruskal and Weiss's fork-join model to account for the effect of event processing time variability on WWT's conservative fixed-window simulation algorithm. A generalization of Thiebaut and Stone's footprint model accurately predicts the effect of cache interference on the CM-5. The model is calibrated using parameters extracted from a fully-parallel simulation (
p
=
N
), and validated by measuring the speedup as the number of processors (
p
) ranges from one to the number of target nodes (
N
. Together with simple cost models, the performance model indicates that for target system sizes of 32 nodes and larger, parallel simulation is more cost-effective than sequential simulation. The key intuition behind this result is that large simulations require large memories, which dominate the cost of a uniprocessor; parallel computers allow multiple processors to simultaneously access this large memory.
Algorithmic state machine implementation with hybrid microprocessing/microprogramming scheme
Authors: Kuo Y. H. , Kung L. Y.
Published: January 2007

This paper proposes a hybrid microprocessing/microprogramming (HMM) scheme to implement the algorithmic state machines (ASM). First, a behavior model of the HMM is defined. This model carries out any task by partitioning it into a microprocessing subtask which is executed by a microprocessor unit and a microprogramming subtask which is executed by a microprogrammed unit. The problems of constructing the microprogrammed unit of HMM are then considered, including the synthesis of control store sequencer, compaction of control store, and microcode generation. Finally, an application example using the above method to design a universal floppy disk controller which can accept all kinds of encoding formats is provided.
The implementation of Prolog via VAX 8600 microcode
Authors: Gee J. , Melvin S. W. , Patt Y. N.
Published: January 2007

We have implemented a high performance Prolog engine by directly executing in microcode the constructs of Warren's Abstract Machine. The implementation vehicle is the VAX 8600 computer. The VAX 8600 is a general purpose processor containing 8K words of writable control store. In our system, each of the Warren Abstract Machine instructions is implemented as a VAX 8600 machine level instruction. Other Prolog built-ins are either implemented directly in microcode or executed by the general VAX instruction set. Initial results indicate that our system is the fastest implementation of Prolog on a commercially available general purpose processor.
The sociology of microprogramming
Authors: Tracz W. J. , Belgard R.
Published: January 2007

Microprogramming is an implementation technique. As computer complexity has risen, it has gained increased importance and wider application. As we proceed through the 80's, we are witness to more specialization and divergence between hardware and software. Hardware trends toward VLSI introduce new tradeoffs that are to be evaluated by design engineers. Concurrency and complex security mechanisms in operating systems and databases have extended the software development discipline to new limits. Each of these examples illustrate the trend toward a larger gap between hardware and software. The purpose of this paper is first, to re-examine the role that microprogramming or firmware engineering plays in the design and implementation of computer systems and, second, to analyze its ability to bridge the gap between hardware and software as perceived and affected by various corporate cultures.
Formally based static analysis of microcode
Authors: Foster J. M.
Published: January 2007

Algebraic methods have been widely used to find properties of programs, especially for use in compiler optimisation. This paper describes the use of this kind of method to prove the absence of particular errors in microcode, or to detect and locate such errors. In order to show the kind of error which may be found we consider a number of examples. All of these have found errors in practical microcode, written for the PERQ computer.
The human factors of speech-based interfaces
Authors: Bradford James H.
Published: January 2007

This article outlines some of the characteristics of speech technology that distinguish it from traditional interaction techniques. A number of human factors issues relating to speech will be discussed in the context of a proposed research agenda for speech-based interfaces.
Is APL2 a good programming language?
Authors: Beaumont Nicholas
Published: January 2007

This paper evaluates APL2 in the context of systems development, noting that a language is not an end in itself, but one of several tools used to create an information system. Despite its many good features APL2, when evaluated in that context, has some disadvantages, especially the lack of control structures and data typing. These omissions make finding errors in programs and translating system requirements into programs harder than necessary. These and other disadvantages of APL2 (such as its lack of portability) make its relative unpopularity explicable. Some changes to APL2 are suggested.
Infinity arithmetic, comparisons and J
Authors: Davies Harvey
Published: January 2007

The principles of
infinity arithmetic
are explained. There is a need to bring J arithmetic and comparisons into line with these principles. Many of the results produced by J are mathematically anomalous and do not comply with the IEEE 754 Standard for floating-point arithmetic.

Some proposals to generalise the concept of comparison tolerance are presented. There are also some tentative proposals regarding safety levels and precision.

The paper is oriented towards J but many of the concepts are relevant to all dialects of APL.
Holland classifier systems
Authors: Geyer-Schulz Andreas
Published: January 2007

A Holland classifier system is an adaptive, general purpose machine learning system which is designed to operate in noisy environments with infrequent and often incomplete feedback. Examples of such environments are financial markets, stock management systems, or chemical processes. In financial markets, a Holland classifier system would develop trading strategies, in a stock management system order heuristics, and in a chemical plant it would perform process control. In this paper we describe a Holland classifier system and present the implementation of its components, namely the production system, the bucket brigade algorithm, the genetic algorithm, and the cover detector, cover effector and triggered chaining operator. Finally, we illustrate the working of a Holland classifier system by learning to find a path with a high payoff in a simple finite state world.
Modeling the effects of acid leaching on concrete
Authors: Hartzfeld Kevin
Published: January 2007

This paper describes a partial differential equation model used to determine the service life of buried concrete vaults exposed to acidic ground water. A graphics package helped immeasurably in debugging and testing the algorithm. The collocation program developed in APL can easily be applied to solve other problems.
The philosophy of nothing and everything
Authors: Holmes Neville , Hallam Colin
Published: January 2007

Perhaps inspired by the IEEE floating point arithmetic standard's introduction of a representation for aberrant numbers, such as the reciprocal of zero, the J interpreter overtly deals with infinites and indeterminacies.

This step got rid of some domain error messages, but brought in a few new difficulties, and exposed inconsistencies in the behaviour of elementary arithmetic functions presumably as delivered by the C compilers used for the J interpreters.

This paper proposes notation that would allow the J interpreter better to deal with failures of arithmetic. The discussion should assist development of arithmetic for other interpreters and compilers.
The role of composition in computer programming
Authors: McIntyre Donald B.
Published: January 2007

Iverson has greatly enlarged the mathematical notion of function composition and made it available to computer programmers. This paper explains the concept, and uses practical examples to show how concise, powerful programs can be written and read. Alternative forms are given, and ways of overcoming initial difficulties are explained.

The systematic use of composition extends the well-known advantages of APL; namely conciseness, consistency, and generality.
Computing multivariable Taylor series to arbitrary order
Authors: Neidinger Richard D.
Published: January 2007

Automatic differentiation, manipulating numerical vectors of coefficients, is the efficient way to compute multivariable Taylor series. This does not require symbolic differentiation or numerical approximation but uses exact formulas applied to numerical arrays. Arrays of Taylor series coefficients of any elementary function can be built-up, as the array for each component (combination or function) is a combination of its argument arrays. The functions TIMES and EXP display the algorithmic ideas that enable all of the other standard functions. We study the interesting recursive formulas for these combinations, the resulting algorithms, and the implementation in APL. To handle all coefficients in
n
variables up to order
m
, the arrays are hyper-pyramid data structures, considered conceptually as
n
-dimensional but implemented as one-dimensional arrays. Unlike previous work, this implementation does not require huge arrays for binomial coefficients and indirect referencing. This APL*PLUS III implementation loops through one nested reference array and takes sub-arrays from another for a practical solution to this problem that can make tremendous demands on time and space.
Untying the Gordian knot
Authors: Neitzel Martin
Published: January 2007

The “Dictionary of J” is not written for the faint of heart. Its numerous self-references make it very difficult to tackle. The author thinks that section II.B, “Verbs”, is one of the keys for getting a confident grip of the language. This paper basically just repeats this section using a tutorial style, some historical background, and several pictures. Hopefully, it will enable people with analytical minds to find their own way through the Dictionary. It closes with a discussion of possible language changes in the context of II.B
AVCS
Authors: Puntikov Nikolai I. , Volodin Maxim A. , Kolesnikov Alexei A.
Published: January 2007

This paper described AVCS, which is an APL-oriented version control system devised as a tool to track the history of software projects and to control concurrent access to project components. The basics of version control systems are explained, and specific aspects of applying a version control system methodology to project development in APL environments are considered. Particular attention is given to features which differentiate the approach accepted in AVCS from that of available version control and project management systems. Specification of AVCS's data maintenance, programming and user interface is presented to the extent required in order to explain how the system works. In conclusion, the possible application of AVCS to solving problems of porting APL projects across different environments is outlined.
Namespaces
Authors: Swain Rexford H.
Published: January 2007

This paper describes and contrasts the implementation of namespaces in two popular combinations of APL dialects and platforms: IBM's APL2 (version 2, release 2) running under VM/CMS, and Dyadic's Dyalog APL/W (version 7.0) running under Microsoft Windows.

In a traditional APL workspace, localization is the only mechanism available to isolate identifier names and values, and it is extremely potent. While a function that localizes a given name is executing, it is impossible to reference any other definition of the same name.

Namespaces are a significant addition to an APL system. They provide a way to “package” a collection of objects (variables, defined functions, etc.), and insulate them from the traditional workspace. A namespace co-exists with the workspace, yet its object names and definitions are completely independent of the workspace. Namespaces can help to organize and hide complexity in workspaces, avoid name conflicts, and share code among applications.

IBM has offered namespaces in APL2 since 1987, whereas Dyadic just recently introduced their facility. Both implementations provide encapsulation and name isolation within a workspace. But they use quite different methods to access objects in a namespace and store their initial definitions. The merits of each approach are discussed. An example is provided to illustrate how namespaces may be used to simplify the implementation and improve the functionality of workspace and function analysis tools.
On the signature weight in “multiple”
m
signature files
Authors: Grandi Fabio
Published: January 2007

This paper deals with the estimation of the signature weight as generated by the superimposed coding technique adopted in "multiple" m signature files. The estimation is needed for performance evaluation of such organizations used for information retrieval applications. In particular, simple formulas for the probability density function, the expected value and the variance of the signature weight are presented.The presented formulas can be derived following a general methodology we called the γ-transform approach in a previous work, which results much more simple than the method used by other authors for the derivation of the density function. Equivalence of the results is also shown.
Book review: The Art of Prolog, 2nd edition by Leon Sterling and Ehud Shapiro (MIT Press, 1994)
Authors: Tinkham Nancy Lynn
Published: January 2007

In his 1983 dissertation [1], Ehud Shapiro lamented the lack of literature available on good Prolog programming style. While manuals for the language existed, there was little available to guide a new programmer into the best ways of using the elements of the language to write good programs rather than merely programs that work.
Fortran 95
Authors: ANSI Accredited Technical Subcommittee X3J3 CORPORATE
Published: January 2007

ISO/IEC 1539 is a multipart International Standard; the parts are published separately. This publication, 1539-1, which is the first part, specifies the form and establishes the interpretation of programs expressed in the Fortran language. The purpose of this part is to promote portability, reliability, maintainability, and efficient execution of Fortran programs for use on a variety of computing systems. The second part, 1539-2, defines additional facilities for the manipulation of character strings of variable length. A processor conforming to 1539-1 need not conform to 1539-2; however, conformance to 1539-2 assumes conformance to this part. Throughout this publication, the term "this standard" refers to 1539-1.
Performance predictions for parallel diagonal-implicitly iterated Runge-Kutta methods
Authors: Rauber Thomas , Rünger Gudula
Published: January 2007

Many simulations in the natural sciences and engineering require the numerical solution of nonlinear differential equations. For this class of numerical methods, we propose an appropriate parallel computation model on distributed memory machines that supports the prediction of execution times. As a case study, we investigate the parallel implementation of the diagonal-implicitly iterated Runge-Kutta method, a solution method for stiff systems of ordinary differential equations. An implementation on the Intel iPSC/860 confirms the accuracy of the prediction model.
The treatment of state in optimistic systems
Authors: Bruce David
Published: January 2007

Optimistic computation methods typically save copies of objects' state information, so that they can recover from erroneous “over-optimistic” computations. Such state saving is generally time and space consuming, and can be rather complicated both to implement and to use.

I show how the data structure community's theory of persistence can be used not only to analyse and explain the treatment of state in optimistic systems, but also as a simple yet general mechanism for performing the necessary state saving with minimal impact on application code.

Preliminary results based on a benchmark application and an existing optimistic simulator are presented, showing that providing support for fully general object states is a realistic and practical option. In addition, I show how some existing state saving techniques—including support for shared state—can be derived, and discuss a number of ways in which the model might be extended.
SGTNE
Authors: Boukerche Azzedine , Tropper Carl
Published: January 2007

This paper describes an extension of the TNE algorithm, the objective of which is to increase its parallelism and to break the inter-processor deadlocks inherent with the use of TNE. The algorithm, which we call the SGTNE algorithm (Semi Global TNE), is executed over a cluster of processors as opposed to TNE, which is executed over a cluster of processes assigned to a single processor. SGTNE helps to break the inter-processor deadlocks by executing a shortest path algorithm over a snapshot of the LPs in a cluster of processors. This paper discusses the algorithm and its implementation and reports on the performance results of simulations of a partitioned FCFS queueing network model executed on the Intel Paragon A4 multiprocessor machine. We also examine the impact of partitioning on the efficient implementation of the SGTNE algorithm. The results obtained indicate that SGTNE yields good speedups and that a partitioning which makes use of a strongly connected component algorithm results in a reduction of 30% in the running time of a simulation when compared to simple partitioning strategies. The results also indicate that SGTNE outperforms TNE.
Probabilistic adaptive direct optimism control in Time Warp
Authors: Ferscha Alois
Published: January 2007

In a distributed memory environment the communication overhead of Time Warp as induced by the rollback procedure due to “overoptimistic” progression of the simulation is the dominating performance factor. To limit optimism to an extent that can be justified from the inherent model parallelism, an optimism control mechanism is proposed, which by maintaining a history record of virtual time differences from the time stamps carried by arriving messages, and forecasting the timestamps of forthcoming messages, probabilistically delays the execution of scheduled events to avoid potential rollback and associated communication overhead (antimessages). After investigating statistical forecast methods which express only the central tendency of the arrival process, we demonstrate that arrival processes in the context of Time Warp simulations of timed Petri nets have certain predictable and consistent ARIMA characteristics, which encourage the use of sophisticated and recursive forecast procedures based on those models. Adaptiveness is achieved in two respects: the synchronization behavior of logical processes automatically progressing and conservatively blocking, that is the most adequate for (i) the specific simulation model and (ii) the communication/computation speed characteristics of the underlying execution platform.
Super-criticality revisited
Authors: Srinivasan Sudhir , Reynolds Paul F.
Published: January 2007

Critical path analysis has been suggested as a technique for establishing a lower bound on the completion times of parallel discrete event simulations. A protocol is super-critical if there is at least one simulation that can complete in less than the critical path time using that protocol. Previous studies have shown that several practical protocols are super-critical while others are not. We present a sufficient condition to demonstrate that a protocol is super-criticality. It has been claimed that super-criticality requires independence of one or more messages (states) on events in the logical past of those messages (states). We present an example which contradicts this claim and examine the implications of this contradiction on lower bounds.