Series in Computer Science – serie

THE CONTEXT OF PARALLEL PROCESSING The field of digital computer architecture has grown explosively in the past two decades. Through a steady stream of experimental research, tool-building efforts, and theoretical studies, the design of an instruction-set architecture, once considered an art, has been transformed into one of the most quantitative branches of computer technology. At the same time, better understanding of various forms of concurrency, from standard pipelining to massive parallelism, and invention of architectural structures to support a reasonably efficient and user-friendly programming model for such systems, has allowed hardware performance to continue its exponential growth. This trend is expected to continue in the near future. This explosive growth, linked with the expectation that performance will continue its exponential rise with each new generation of hardware and that (in stark contrast to software) computer hardware will function correctly as soon as it comes off the assembly line, has its down side. It has led to unprecedented hardware complexity and almost intolerable dev- opment costs. The challenge facing current and future computer designers is to institute simplicity where we now have complexity; to use fundamental theories being developed in this area to gain performance and ease-of-use benefits from simpler circuits; to understand the interplay between technological capabilities and limitations, on the one hand, and design decisions based on user and application requirements on the other.

This work introduces the application of the Java programming language in discrete-event simulation. In addition, the fundamental concepts and practical simulation techniques for modelling different types of systems to study their general behaviour and their performance are introduced. The approaches applied are the process interaction approach to discrete-event simulation and object-oriented modelling. Java is used as the implementation language and UML as the modelling language. The first offers several advantages compared to C++, the most important being thread handling, graphical user interfaces (GUI), and Web computing. The second language, UML (Unified Modeling Language), is the standard notation used today for modelling systems as a collection of classes, class relationships, objects, and object behaviour. The book concentrates on object-oriented modelling and implementation aspects of simulation models using Java and practical simulation techniques. In addition, the book illustrates the dynamic behaviour of systems using the various simulation models as case studies.

With the advent of portable and autonomous computing systems, power con­ sumption has emerged as a focal point in many research projects, commercial systems and DoD platforms. One current research initiative, which drew much attention to this area, is the Power Aware Computing and Communications (PAC/C) program sponsored by DARPA. Many of the chapters in this book include results from work that have been supported by the PACIC program. The performance of computer systems has been tremendously improving while the size and weight of such systems has been constantly shrinking. The capacities of batteries relative to their sizes and weights has been also improv­ ing but at a rate which is much slower than the rate of improvement in computer performance and the rate of shrinking in computer sizes. The relation between the power consumption of a computer system and it performance and size is a complex one which is very much dependent on the specific system and the technology used to build that system. We do not need a complex argument, however, to be convinced that energy and power, which is the rate of energy consumption, are becoming critical components in computer systems in gen­ eral, and portable and autonomous systems, in particular. Most of the early research on power consumption in computer systems ad­ dressed the issue of minimizing power in a given platform, which usually translates into minimizing energy consumption, and thus, longer battery life.

Based on his experiences and contributions, the author discusses electronic negotiation technologies - key ingredients for the next generation of electronic markets - from a scientific as well as a practitioner's perspective. He reviews the state-of-the-art and then introduces novel support mechanisms and design elements, which are applied in a number of case studies. This book is geared towards technicians interested in e-Commerce application development but also offers extensive background reading for educational purposes.

The Structural Theory of Probability addresses the interpretation of probability, often debated in the scientific community. This problem has been examined for centuries; perhaps no other mathematical calculation suffuses mankind's efforts at survival as amply as probability. In the dawn of the 20th century David Hilbert included the foundations of the probability calculus within the most vital mathematical problems; Dr. Rocchi's topical and ever-timely volume proposes a novel, exhaustive solution to this vibrant issue.Paolo Rocchi, a versatile IBM scientist, outlines a new philosophical and mathematical approach inspired by well-tested software techniques. Through the prism of computer technology he provides an innovative view on the theory of probability. Dr. Rocchi discusses in detail the mathematical tools used to clarify the meaning of probability, integrating with care numerous examples and case studies. The comprehensiveness and originality of its mathematical development make this volume an inspiring read for researchers and students alike.

Parallel computing is a frontier technology on the fringes of mainstream computing, yet its much-heralded triumph over sequential computing has yet to materialize. This is in spite of the fact that the processing needs of many signal processing applications continue to eclipse the capabilities of sequential computing. The culprit is largely the software development environment. Fundamental shortcomings in the development environment of many parallel computer architectures thwart the adoption of parallel computing. Foremost, parallel computing has no unifying model to accurately predict the execution time of algorithms on parallel architectures. Cost and scarce programming resources prohibit deploying multiple algorithms and partitioning strategies in attempt to find the fastest solution. As a consequence, algorithm design is largely an intuitive art form dominated by practitioners who specialize in a particular computer architecture. This, coupled with the fact that parallel computer architectures rarely last more than a couple of years, makes for a complex and challenging design environment.To navigate this environment, algorithm designers need a road map, a detailed procedure they can use to efficiently develop high performance, portable parallel algorithms. The focus of this book is to draw such a road map. The parallel algorithm synthesis procedure can be used to design reusable building blocks of adaptable, scalable software modules from which high performance signal processing applications can be constructed. The hallmark of the procedure is a semi-systematic process for introducing parameters to control the partitioning and scheduling of computation and communication. This facilitates the tailoring of software modules to exploit different configurations of multiple processors, multiple floating-point units, and hierarchical memories. To showcase the efficacy of this procedure, the book presents three case studies requiring various degrees of optimization for parallel execution. This book can be used as a reference for algorithm designers or as a text for an advanced course on parallel programming.

Parallel job scheduling has been extensively studied over the last two decades of the 20th century. Initial focus of these studies has been on small UMA architectures. More recent interest is in the cluster systems. A job scheduling policy that works effectively for small UMA systems might not work for large distributed-memory systems with thousands of processors. Thus, scalability is an important characteristic of a scheduling policy if we want to use it in large distributed-memory systems. In this book, the author presents a hierarchical scheduling policy to fit in with system size. This policy is based on the hierarchical task queue organization he introduced to organize the system run queue. The book is divided into four parts. Part I gives introduction to parallel and cluster systems. It also provides an overview of parallel job scheduling policies proposed in the literature. Part II gives details about the hierarchical task queue organization and its performance. The author shows that this organization scales well, which makes it suitable for systems with hundreds to thousands of processors.In Part III he uses this task queue organization as the basis to devise hierarchical scheduling policies for shared-memory and distributed-memory parallel systems as well as cluster systems. This part demonstrates that the hierarchical policy provides substantial performance advantages over other policies proposed in the literature. Finally, Part IV concludes the book with a brief summary and concluding remarks.

"Mobile IP: Present State and Future" is an up-to-date introduction to the rapidly evolving field of mobile IP. In addition to detailed coverage of motivation behind mobile IP and fundamental concepts of mobile IP like agent advertisement and discovery, registration and tunneling, the book provides a comprehensive treatment of various associated technical issues such as security, TCP performance, multicasting and integration with wireless. The book has been written to serve as a text for network professionals who are yearning to acquire a clear understanding of this interesting field.

Modern applications are both data and computationally intensive and require the storage and manipulation of voluminous traditional (alphanumeric) and nontraditional data sets (images, text, geometric objects, time-series). Examples of such emerging application domains are: Geographical Information Systems (GIS), Multimedia Information Systems, CAD/CAM, Time-Series Analysis, Medical Information Sstems, On-Line Analytical Processing (OLAP), and Data Mining. These applications pose diverse requirements with respect to the information and the operations that need to be supported. From the database perspective, new techniques and tools therefore need to be developed towards increased processing efficiency.This monograph explores the way spatial database management systems aim at supporting queries that involve the space characteristics of the underlying data, and discusses query processing techniques for nearest neighbor queries. It provides both basic concepts and state-of-the-art results in spatial databases and parallel processing research, and studies numerous applications of nearest neighbor queries.

Hard real-time systems are very predictable, but not sufficiently flexible to adapt to dynamic situations. They are built under pessimistic assumptions to cope with worst-case scenarios, so they often waste resources. Soft real-time systems are built to reduce resource consumption, tolerate overloads and adapt to system changes. They are also more suited to novel applications of real-time technology, such as multimedia systems, monitoring apparatuses, telecommunication networks, mobile robotics, virtual reality, and interactive computer games. This unique monograph provides concrete methods for building flexible, predictable soft real-time systems, in order to optimize resources and reduce costs. It is an invaluable reference for developers, as well as researchers and students in Computer Science.

With the advent of portable and autonomous computing systems, power con­ sumption has emerged as a focal point in many research projects, commercial systems and DoD platforms. One current research initiative, which drew much attention to this area, is the Power Aware Computing and Communications (PAC/C) program sponsored by DARPA. Many of the chapters in this book include results from work that have been supported by the PACIC program. The performance of computer systems has been tremendously improving while the size and weight of such systems has been constantly shrinking. The capacities of batteries relative to their sizes and weights has been also improv­ ing but at a rate which is much slower than the rate of improvement in computer performance and the rate of shrinking in computer sizes. The relation between the power consumption of a computer system and it performance and size is a complex one which is very much dependent on the specific system and the technology used to build that system. We do not need a complex argument, however, to be convinced that energy and power, which is the rate of energy consumption, are becoming critical components in computer systems in gen­ eral, and portable and autonomous systems, in particular. Most of the early research on power consumption in computer systems ad­ dressed the issue of minimizing power in a given platform, which usually translates into minimizing energy consumption, and thus, longer battery life.

Modern applications are both data and computationally intensive and require the storage and manipulation of voluminous traditional (alphanumeric) and nontraditional data sets (images, text, geometric objects, time-series). Examples of such emerging application domains are: Geographical Information Systems (GIS), Multimedia Information Systems, CAD/CAM, Time-Series Analysis, Medical Information Sstems, On-Line Analytical Processing (OLAP), and Data Mining. These applications pose diverse requirements with respect to the information and the operations that need to be supported. From the database perspective, new techniques and tools therefore need to be developed towards increased processing efficiency.This monograph explores the way spatial database management systems aim at supporting queries that involve the space characteristics of the underlying data, and discusses query processing techniques for nearest neighbor queries. It provides both basic concepts and state-of-the-art results in spatial databases and parallel processing research, and studies numerous applications of nearest neighbor queries.

Hard real-time systems are very predictable, but not sufficiently flexible to adapt to dynamic situations. They are built under pessimistic assumptions to cope with worst-case scenarios, so they often waste resources. Soft real-time systems are built to reduce resource consumption, tolerate overloads and adapt to system changes. They are also more suited to novel applications of real-time technology, such as multimedia systems, monitoring apparatuses, telecommunication networks, mobile robotics, virtual reality, and interactive computer games. This unique monograph provides concrete methods for building flexible, predictable soft real-time systems, in order to optimize resources and reduce costs. It is an invaluable reference for developers, as well as researchers and students in Computer Science.

Despite five decades of research, parallel computing remains an exotic, frontier technology on the fringes of mainstream computing. Its much-heralded triumph over sequential computing has yet to materialize. This is in spite of the fact that the processing needs of many signal processing applications continue to eclipse the capabilities of sequential computing. The culprit is largely the software development environment. Fundamental shortcomings in the development environment of many parallel computer architectures thwart the adoption of parallel computing. Foremost, parallel computing has no unifying model to accurately predict the execution time of algorithms on parallel architectures. Cost and scarce programming resources prohibit deploying multiple algorithms and partitioning strategies in an attempt to find the fastest solution. As a consequence, algorithm design is largely an intuitive art form dominated by practitioners who specialize in a particular computer architecture. This, coupled with the fact that parallel computer architectures rarely last more than a couple of years, makes for a complex and challenging design environment.To navigate this environment, algorithm designers need a road map, a detailed procedure they can use to efficiently develop high performance, portable parallel algorithms. The focus of this book is to draw such a road map. The Parallel Algorithm Synthesis Procedure can be used to design reusable building blocks of adaptable, scalable software modules from which high performance signal processing applications can be constructed. The hallmark of the procedure is a semi-systematic process for introducing parameters to control the partitioning and scheduling of computation and communication. This facilitates the tailoring of software modules to exploit different configurations of multiple processors, multiple floating-point units, and hierarchical memories. To showcase the efficacy of this procedure, the book presents threecase studies requiring various degrees of optimization for parallel execution.

Mobile IP: Present State and Future is an up-to-date introduction to the rapidly evolving field of mobile IP. In addition to detailed coverage of motivation behind mobile IP and fundamental concepts of mobile IP like agent advertisement and discovery, registration and tunneling, the book provides a comprehensive treatment of various associated technical issues such as security, TCP performance, multicasting and integration with wireless. The book has been written to serve as a text for network professionals who are yearning to acquire a clear understanding of this interesting field.

The Structural Theory of Probability addresses the interpretation of probability, often debated in the scientific community. This problem has been examined for centuries; perhaps no other mathematical calculation suffuses mankind's efforts at survival as amply as probability. In the dawn of the 20th century David Hilbert included the foundations of the probability calculus within the most vital mathematical problems; Dr. Rocchi's topical and ever-timely volume proposes a novel, exhaustive solution to this vibrant issue.Paolo Rocchi, a versatile IBM scientist, outlines a new philosophical and mathematical approach inspired by well-tested software techniques. Through the prism of computer technology he provides an innovative view on the theory of probability. Dr. Rocchi discusses in detail the mathematical tools used to clarify the meaning of probability, integrating with care numerous examples and case studies. The comprehensiveness and originality of its mathematical development make this volume an inspiring read for researchers and students alike.

Multiple processor systems are an important class of parallel systems. Over the years, several architectures have been proposed to build such systems to satisfy the requirements of high performance computing. These architectures span a wide variety of system types. At the low end of the spectrum, we can build a small, shared-memory parallel system with tens of processors. These systems typically use a bus to interconnect the processors and memory. Such systems, for example, are becoming commonplace in high-performance graph­ ics workstations. These systems are called uniform memory access (UMA) multiprocessors because they provide uniform access of memory to all pro­ cessors. These systems provide a single address space, which is preferred by programmers. This architecture, however, cannot be extended even to medium systems with hundreds of processors due to bus bandwidth limitations. To scale systems to medium range i. e. , to hundreds of processors, non-bus interconnection networks have been proposed. These systems, for example, use a multistage dynamic interconnection network. Such systems also provide global, shared memory like the UMA systems. However, they introduce local and remote memories, which lead to non-uniform memory access (NUMA) architecture. Distributed-memory architecture is used for systems with thousands of pro­ cessors. These systems differ from the shared-memory architectures in that there is no globally accessible shared memory. Instead, they use message pass­ ing to facilitate communication among the processors. As a result, they do not provide single address space.

Michael Ströbel worked for several years as a software engineer and consultant in the German IT industry before joining IBM Research in Switzerland, where he developed his interest in support for negotiations in electronic markets. During his career in research, he has published several articles on this topic in major international conferences and journals and received a PhD from the University of St.Gallen, Switzerland.Based on his experiences and contributions, the author discusses electronic negotiation technologies - key ingredients for the next generation of electronic markets - from a scientific as well as a practitioner's perspective. He reviews the state-of-the-art and then introduces novel support mechanisms and design elements, which are applied in a number of case studies. This book is geared towards technicians interested in E-Commerce application development but also offers extensive background reading for educational purposes.

Researches and developers of simulation models state that the Java program­ ming language presents a unique and significant opportunity for important changes in the way we develop simulation models today. The most important characteristics of the Java language that are advantageous for simulation are its multi-threading capabilities, its facilities for executing programs across the Web, and its graphics facilities. It is feasible to develop compatible and reusable simulation components that will facilitate the construction of newer and more complex models. This is possible with Java development environments. Another important trend that begun very recently is web-based simulation, i.e., and the execution of simulation models using Internet browser software. This book introduces the application of the Java programming language in discrete-event simulation. In addition, the fundamental concepts and prac­ tical simulation techniques for modeling different types of systems to study their general behavior and their performance are introduced. The approaches applied are the process interaction approach to discrete-event simulation and object-oriented modeling. Java is used as the implementation language and UML as the modeling language. The first offers several advantages compared to C++, the most important being: thread handling, graphical user interfaces (QUI) and Web computing. The second language, UML (Unified Modeling Language) is the standard notation used today for modeling systems as a collection of classes, class relationships, objects, and object behavior.

THE CONTEXT OF PARALLEL PROCESSING The field of digital computer architecture has grown explosively in the past two decades. Through a steady stream of experimental research, tool-building efforts, and theoretical studies, the design of an instruction-set architecture, once considered an art, has been transformed into one of the most quantitative branches of computer technology. At the same time, better understanding of various forms of concurrency, from standard pipelining to massive parallelism, and invention of architectural structures to support a reasonably efficient and user-friendly programming model for such systems, has allowed hardware performance to continue its exponential growth. This trend is expected to continue in the near future. This explosive growth, linked with the expectation that performance will continue its exponential rise with each new generation of hardware and that (in stark contrast to software) computer hardware will function correctly as soon as it comes off the assembly line, has its down side. It has led to unprecedented hardware complexity and almost intolerable dev- opment costs. The challenge facing current and future computer designers is to institute simplicity where we now have complexity; to use fundamental theories being developed in this area to gain performance and ease-of-use benefits from simpler circuits; to understand the interplay between technological capabilities and limitations, on the one hand, and design decisions based on user and application requirements on the other.

This book introduces the fundamental concepts and practical simulation te- niques for modeling different aspects of operating systems to study their g- eral behavior and their performance. The approaches applied are obje- oriented modeling and process interaction approach to discrete-event simu- tion. The book depends on the basic modeling concepts and is more specialized than my previous book: Practical Process Simulation with Object-Oriented Techniques and C++, published by Artech House, Boston 1999. For a more detailed description see the Web location: http://science.kennesaw.edu/~jgarrido/mybook,html. Most other books on performance modeling use only analytical approaches, and very few apply these concepts to the study of operating systems. Thus, the unique feature of the book is that it concentrates on design aspects of operating systems using practical simulation techniques. In addition, the book illustrates the dynamic behavior of different aspects of operating systems using the various simulation models, with a general hands-on approach.

Dynamic Reconfiguration: Architectures and Algorithms offers a comprehensive treatment of dynamically reconfigurable computer architectures and algorithms for them. The coverage is broad starting from fundamental algorithmic techniques, ranging across algorithms for a wide array of problems and applications, to simulations between models. The presentation employs a single reconfigurable model (the reconfigurable mesh) for most algorithms, to enable the reader to distill key ideas without the cumbersome details of a myriad of models. In addition to algorithms, the book discusses topics that provide a better understanding of dynamic reconfiguration such as scalability and computational power, and more recent advances such as optical models, run-time reconfiguration (on FPGA and related platforms), and implementing dynamic reconfiguration. The book, featuring many examples and a large set of exercises, is an excellent textbook or reference for a graduate course. It is also a useful reference to researchers and system developers in the area.

This book provides an overview of the X Window System focusing on characteristics that have significant impact on the development of both application programs and widgets. We pay special attention to applications that go beyond graphical user interfaces (GUIs); therefore we discuss issues affecting video games, visualization and imaging programs, and designing widgets with a complex appearance. While the book does not assume previous knowledge of X, it is intended for experienced programmers, especially those who want to write programs that go beyond simple GUIs. X is the dominant window system under Unix, and X servers are available for Microsoft Windows, thus enabling graphics over a network in the PC world. While Java offers an apparently universal graphics library (the abstract window toolkit), the reality is quite different: For high-quality graphics and image display, we must program on the target platform itself (X or one of Microsoft’s APIs) rather than rely on Java peer objects. X is a vast subject, so it is impossible to provide a complete coverage in a few hundred pages. Thus we selected topics that are fundamental to the system, so that the reader who masters them should be able to read the documentation of the numerous libraries and toolkits. Therefore we provide documentation on the most important Xlib and X toolkit functions only.