A basic problem faced by designers of high-bandwidth switches and routers is to provide effective techniques for scheduling the routing of cells through crossbars. The problem is particularly important under heavy loads or when quality-of-service (QoS) is to be supported. Much previous work on scheduling has focused on maximum bipartite matching (MBM), maximum weight bipartite matching (MWBM), and heuristics to approximate MBM and MWBM solutions. In this paper, we introduce the shakeup technique: a randomized approach that can be used in conjunction with a number of existing heuristics to substantially improve solution quality. The shakeup approach is conceptually simple and is supported by both theoretical and experimental results. In addition, this paper provides for the first time a framework for experimental scheduler analysis. We give extensive head-to-head comparisons of stability ranges for a number of previously proposed schedulers, and work towards the development of benchmark traffic types.

Article BOS is boss: a case for bulk-synchronous object systems Share on Authors: Mark W. Goudreau C&C Research Laboratories, NEC USA, Inc., 4 Independence Way, Princeton, NJ C&C Research Laboratories, NEC USA, Inc., 4 Independence Way, Princeton, NJView Profile , Kevin Lang NEC Research Institute, 4 Independence Way, Princeton, NJ NEC Research Institute, 4 Independence Way, Princeton, NJView Profile , Girija Narlikar School of Computer Science, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA School of Computer Science, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PAView Profile , Satish B. Rao NEC Research Institute, 4 Independence Way, Princeton, NJ NEC Research Institute, 4 Independence Way, Princeton, NJView Profile Authors Info & Claims SPAA '99: Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architecturesJune 1999 Pages 115–125https://doi.org/10.1145/305619.305632Published:01 June 1999 1citation206DownloadsMetricsTotal Citations1Total Downloads206Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The Bulk-Synchronous Parallel (BSP) model was proposed by Valiant as a standard interface between parallel software and hardware. In theory, the BSP model has been shown to allow the asymptotically optimal execution of architecture independent software on a variety of architectures. Our goal in this work is to experimentally examine the practical use of the BSP model on current parallel architectures. We describe the design and implementation of the Green BSP Library, a small library of functions that implement the BSP model, and of several applications that were written for this library. We then discuss the performance of the library and application programs on several parallel architectures. Our results are positive in that we demonstrate efficiency and portability over a range of parallel architectures and show that the BSP cost model is useful for predicting performance trends and estimating execution times.

BSPlib is a small communications library for bulk synchronous parallel (BSP) programming which consists of only 20 basic operations. This paper presents the full definition of BSPlib in C, motivates the design of its basic operations, and gives examples of their use. The library enables programming in two distinct styles: direct remote memory access (DRMA) using put or get operations, and bulk synchronous message passing (BSMP). Currently, implementations of BSPlib exist for a variety of modern architectures, including massively parallel computers with distributed memory, shared memory multiprocessors, and networks of workstations. BSPlib has been used in several scientific and industrial applications; this paper briefly describes applications in benchmarking, Fast Fourier Transforms (FFTs), sorting, and molecular dynamics.

Article Towards efficiency and portability: programming with the BSP model Share on Authors: Mark Goudreau Department of Computer Science, University of Central Florida, Orlando, FL Department of Computer Science, University of Central Florida, Orlando, FLView Profile , Kevin Lang NEC Research Institute, 4 Independence Way, Princeton, NJ NEC Research Institute, 4 Independence Way, Princeton, NJView Profile , Satish Rao NEC Research Institute, 4 Independence Way, Princeton, NJ and University of California at Berkeley, Berkeley, CA NEC Research Institute, 4 Independence Way, Princeton, NJ and University of California at Berkeley, Berkeley, CAView Profile , Torsten Suel NEC Research Institute, 4 Independence Way, Princeton, NJ and University of California at Berkeley, Berkeley, CA NEC Research Institute, 4 Independence Way, Princeton, NJ and University of California at Berkeley, Berkeley, CAView Profile , Thanasis Tsantilas Department of Computer Science, Columbia University, New York, NY Department of Computer Science, Columbia University, New York, NYView Profile Authors Info & Claims SPAA '96: Proceedings of the eighth annual ACM symposium on Parallel Algorithms and ArchitecturesJune 1996 Pages 1–12https://doi.org/10.1145/237502.237503Online:24 June 1996Publication History 45citation447DownloadsMetricsTotal Citations45Total Downloads447Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

It is often difficult to predict the optimal neural network size for a particular application. Constructive or destructive methods that add or subtract neurons, layers, connections, etc. might offer a solution to this problem. We prove that one method, recurrent cascade correlation, due to its topology, has fundamental limitations in representation and thus in its learning capabilities. It cannot represent with monotone (i.e., sigmoid) and hard-threshold activation functions certain finite state automata. We give a "preliminary" approach on how to get around these limitations by devising a simple constructive training method that adds neurons during training while still preserving the powerful fully-recurrent structure. We illustrate this approach by simulations which learn many examples of regular grammars that the recurrent cascade correlation method is unable to learn.

We examine the representational capabilities of first-order and second-order single-layer recurrent neural networks (SLRNN's) with hard-limiting neurons. We show that a second-order SLRNN is strictly more powerful than a first-order SLRNN. However, if the first-order SLRNN is augmented with output layers of feedforward neurons, it can implement any finite-state recognizer, but only if state-splitting is employed. When a state is split, it is divided into two equivalent states. The judicious use of state-splitting allows for efficient implementation of finite-state recognizers using augmented first-order SLRNN's.

The problem of establishing point-to-point communication routes in a random multistage interconnection network (RMIN) is addressed. A neural network routing scheme is presented. This routing scheme is compared to two more traditional routing techniques—namely, exhaustive search routing and greedy routing. The main criterion that is examined is the ability of each routing methodology to solve routing problems. Results are obtained through simulation of the routing methodologies for three different RMINs. The sample RMINs are relatively small since the neural network router in its present form will only be competitive for small RMINs. The simulations show that the three routing schemes perform similarly for the three sample RMINs. Other criteria that will be touched upon are the speed and the resource utilization of each routing methodology and the pros and cons of each approach will be discussed. The results suggest that neural network routers may be appropriate for some communication applications involving RMINs.