Physical Sciences and Mathematics Commons^™

Adaptive Multicast Routing In Wormhole Networks, Ran Libeskind-Hadas, Tom Hehre '96, Andrew Hutchings '98, Mark Reyes '98, Kevin Watkins '97

All HMC Faculty Publications and Research

Multicast communication has applications in a number of fundamental operations in parallel computing. An effective multicast routing algorithm must be free from both livelock and deadlock while minimizing communication latency. We describe two classes of multicast wormhole routing algorithms that employ the multi-destination wormhole hardware mechanism proposed by Lin et al. [12] and Panda et al. [17]. Specific examples of these classes of algorithms are described and experimental results suggests that such algorithms enjoy low communication latencies across a range of network loads.

Random Number Generators For Parallel Computers, Paul D. Coddington

Northeast Parallel Architecture Center

Random number generators are used in many applications, from slot machines to simulations of nuclear reactors. For many computational science applications, such as Monte Carlo simulation, it is crucial that the generators have good randomness properties. This is particularly true for large-scale simulations done on high-performance parallel computers. Good random number generators are hard to find, and many widely-used techniques have been shown to be inadequate. Finding high-quality, efficient algorithms for random number generation on parallel computers is even more difficult. Here we present a review of the most commonly-used random number generators for parallel computers, and evaluate each generator …

Efficient Implementation Of Image Compression-Postprocessing Algorithm Using A Digital Signal Processor, Nadir Sinaceur

Dissertations and Theses

In this thesis, an attempt has been made to develop a fast way to implement a post-processing algorithm for image compression. All the previous tests for this postprocessing algorithm, which we will present, have been only software based and did not consider the time parameter.

For this purpose a new algorithm is used to compute the 2-D DCT transform. This change made the process a lot faster on a Spare 5 workstation. We have then decided to further increase the speed of the post-processing scheme by implementing it on the ADSP21020 chip.

The results show that such a chip can …

A Compiler Algorithm For Optimizing Locality In Loop Nests, Mahmut Kandemir, J. Ramanujam, Alok Choudhary

Electrical Engineering and Computer Science - All Scholarship

This paper describes an algorithm to optimize cache locality in scientific codes on uniprocessor and multiprocessor machines. A distinctive characteristic of our algorithm is that it considers loop and data layout transformations in a unified framework. We illustrate through examples that our approach is very effective at reducing cache misses and tile size sensitivity of blocked loop nests; and can optimize nests for which optimization techniques based on loop transformations alone are not successful. An important special case is the one in which data layouts of some arrays are fixed and cannot be changed. We show how our algorithm can …

Single-Layer Channel Routing And Placement With Single-Sided Nets, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

This paper considers the optimal offset, feasible offset, and optimal placement problems for a more general form of single-layer VLSI channel routing than has usually been considered in the past. Most prior works require that every net has exactly one terminal on each side of the channel. As long as only one side of the channel contains multiple terminals of the same net, we provide linear-time solutions to all three problems. Such results are implausible if the placement of terminals is entirely unrestricted; in fact, the size of the output for the feasible offset problem may be Ω(n^2). The linear-time …

On Three Dimensional Digital Topology And Its Application To Image Processing., Punam Kumar Saha Dr.

Doctoral Theses

Digital topology provides a sound mathematical basis for object classification, counting and labeling, border tracking, contour filling, thinning, segmentation and many other image processing applications. An important characteristic of topo- logical properties is that they are invariant under translation, rotation, and more generally under any elastic deformation. The analysis of three dimensional (3D) digital images has generated increasing interest with the rapid growth of 3D image processing applications including computer vision. 3D digital images are common input/output media in the several application domains of image processing, pattern recognition and computer vision among which 3D medical imaging is of particular interest. …

Design,Analysis And Routing In Static Interconnection Networks., Rajib Kumar Das Dr.

Doctoral Theses

Many real-life applications such as image processing, weather forecasting, digital signal processing, etc., require large amount of computations. By distributing the task among several processors, one can appreciably reduce the computation time. To solve complex problems, several computer architectures using multiple processors have been introduced. Recent developments in IC technology have made it economically feasible to construct multiple processor systems consisting of hundreds or thousands of processors.There are two types of multiprocessor systems (PS87). One is tightly coupled, where the processors share a common clock and/or memory. The other is loosely coupled, where each processor runs independently with a local …

Variable Step Size Lms Adaptive Filters With Delayed Coefficient Updating, Guixian Xu

Electrical & Computer Engineering Theses & Dissertations

A new approach to delayed LMS adaptive filtering is presented, which uses a variable step size for coefficient updating to increase convergence speed and improve tracking characteristics. The new algorithm, called delayed variable step size LMS (DVLMS), is explained, analyzed, and simulated to experimentally determine performance characteristics. Three different strategies for adjusting the step size are examined, and their performance is compared. Also, simulation results are presented to show that the proposed DVLMS systems provide faster convergence and lower mis-adjustment than previously proposed DLMS systems.

Low-Degree Spanning Trees Of Small Weight, Samir Khuller, Balaji Raghavachari, Neal Young

Dartmouth Scholarship

Given n points in the plane, the degree-K spanning-tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most K. This paper addresses the problem of computing low-weight degree-K spanning trees for $K > 2$. It is shown that for an arbitrary collection of n points in the plane, there exists a spanning tree of degree 3 whose weight is at most 1.5 times the weight of a minimum spanning tree. It is shown that there exists a spanning tree of degree 4 whose weight is at most 1.25 times …

Continuous Deformation Of A Developable Surface, Chili Ping Hsu

Mathematics Technical Papers - Archive

A developable surface can be developed from a piece of planar region, or vice versa. Several methods are known to construct an isometric mapping between the developable and the planar region. A simple and efficient algorithm based on the differential geometry and differential equations is presented to construct such an isometric mapping. This algorithm contains a deformation parameter ^, where ^ varies between 0 and 1, that can trace the development of the surface in a fashion that ^ = 0 corresponds to the planar region and ^ = 1 recovers the developable. An error estimation shows the error, in …

Unsupervised Algorithms For Learning Emergent Spatio-Temporal Correlations, Chaitanya Tumuluri

Electrical Engineering and Computer Science - Technical Reports

Many applications require the extraction of spatiotemporal correlations among dynamically emergent features of non-stationary distributions. In such applications it is not possible to obtain an a priori analytical characterization of the emergent distribution. This paper extends the Growing Cell Structures (GCS) network and presents two novel (GIST and GEST) networks, which combine unsupervised feature-extraction and Hebbian learning, for tracking such emergent correlations. The networks were successfully tested on the challenging Data Mapping problem, using an execution driven simulation of their implementation in hardware. The results of the simulations show the successful use of the GIST and GEST networks for extracting …

Torus Routing In The Presence Of Multicasts, Hiroki Ishibashi

Theses Digitization Project

No abstract provided.

On Texture Image Analysis Using Fractal Geometry Based Features., Nirupam Sarkar Dr.

Doctoral Theses

Visual textureTexture is a property to characterize a region of a scene. A set of natural texture images is shown in Fig. 1.1. A specific texture may be generated due to certain organization of several objects in a region, or due to the reflectance pattern caused by color variation or unevenness of an object surface. Since texture provides a lot of information of a region, texture analysis and synthesis are important components of digital image processing.It is difficult to provide a formal definition of texture although we perceive and recognize texture rather easily. According to Sklansky [152) "A region in …

Neuro-Fuzzy Models For Classification And Rule Generation., Sushmita Mitra Dr.

Doctoral Theses

Machine recognition [1, 2] of patterns can be viewed as a two-fold task, consisting of learning the invariant and common properties of a set of samples characterizing a class, and of deciding a new sample as a possible member of the class by noting that it has properties common to those of the set of samples. In other words, pattern recognition by computers can be described as a transformation from the measurenment space M to the feature space F and finally to the decision space D (1), i.e., M ⟶F⟶D.Here, the mapping 6 : F⟶D is the decision function and …

Connectionist Models For Certain Tasks Related To Object Recognition., Jayanta Basak Dr.

Doctoral Theses

Recognition of objects in an image, according to Suetens et al. [1), relers to the task of finding and labeling parts of a two-dimensional image of a scene that correspond to the real objects in the scene. Object recognition is necessary in a variety of domains like robot navigation, aerial imagery analysis, industrial inspection and so on. Normally, different strategies for object recognition (1-(5] involve establishing some model for each object, i.e., some general description of each object, and then labeling different parts of the scene according to the knowledge about the models.Object models can have two-dimensional (2D) or three-climensional …

On Detection And Use Of Reflectional Symmetry In Computer Vision., Dipti Prasad Mukherjee Dr.

Doctoral Theses

The problems of detection and use of reflectional symmetry in the images of planar shape contours are studied. Symmetry, in general, provides important shape representation cues, some of which we utilise here, to acquire viewpoint information and, towards model based shape matching. We concentrate on local reflectional symmetries of emoothly curved planar objecta, though the methoda are equally applicable to polygonal objects; even this could be extended to certain three-dimensional shapes and for other object relations such as rotational symmetry.Under the affine or perspective approximation to image projection, properties of geometrie invariance are used to find (reflectional) symmetric contour pairs. …

Open-Loop State-Space Model Identification From Closed-Loop Data, Lori Guy

Mechanical & Aerospace Engineering Theses & Dissertations

This thesis provides an investigation of a system identification algorithm which identifies an open-loop state-space model from a linear system that is operating under closed-loop conditions. In order to investigate the system identification algorithm some basic ideas of system identification theory are reviewed. Examples using simulated data are presented to characterize the effects of varying the parameters for open-loop and closed-loop system identification processes. Both noise· free and noise contaminated cases are simulated. Linear Quadratic Gaussian (LQG) control theory is reviewed and the motivation for using iterative LQG control feedback is discussed. The derivation of the proposed system identification algorithm …

Polygonal Approximation And Scale-Space Analysis Of Closed Digital Curves., Bimal Kumar Roy Dr.

Doctoral Theses

This thesis presents a series of algorithms for polygonal approximation of closed digital curves followed by scale-space analysis with its application to corner detection.Approximation of a closed curve by plece straight line segments is known as polygonal approximation. Any curve can be approximated by a polygon with any desired degree of accuracy.Polygonal approximation is useful in reducing the number of points required to represent a curve and to smooth data. Such representation facilitates extraction of numerical features for description and classification of curves. Basically there are two approaches to the problem. One is to subdivide the points into groups each …

Some Contributions To Linear Complementarity Problem., G. S. R. Murthy Dr.

Doctoral Theses

This dissertation deals with a number of problems related to linear comple- mentarity problem (LCP). Given a real square matrix A of order n and a real n-vector q, the LCP is to find a nonnegative n-vector z such that Az + q 2 0 and zt(Az + 9) = 0. There is vast literature on LCP, evolved during the last four decades. LCP plays a crucial role in the study of mathematical program- ming from the view point of algorithms as well as applications. The inherent nature of the problem has led the researchers to introduce and study a …

Approximation Algorithms: Good Solutions To Hard Problems, Ran Libeskind-Hadas

All HMC Faculty Publications and Research

Consider a computer network represented by an undirected graph where the vertices represent computer nodes and the edges represent links between the nodes. Since some of the links in the network may become faulty, link testing devices are placed at some of the nodes. A tester at a particular node can test all links incident to that node. Since the testers are expensive, however, we wish to deploy the minimum number of these devices such that every link is incidient to at least one node containing a tester. In graph theoretic terms, a vertex cover is a subset of the …

Automatic Pcb Inspection Systems, M. Moganti, Fikret Erçal

Computer Science Faculty Research & Creative Works

There are more than 50 process steps required to fabricate a printed circuit board (PCB). To ensure quality, human operators simply inspect the work visually against prescribed standards. The decisions made by this labor intensive, and therefore costly, procedure often also involve subjective judgements. Automatic inspection systems remove the subjective aspects and provide fast, quantitative dimensional assessments. Machine vision may answer the manufacturing industry's need to improve product quality and increase productivity. The major limitation of existing inspection systems is that all the algorithms need a special hardware platform to achieve the desired real-time speeds. This makes the systems extremely …

Studies On Design, Routing And Fault Tolerance Of Interconnection Network., Krishnendu Mukhopadhyay Dr.

Doctoral Theses

A recent trend in computing is to distribute the computations among a set of processing elements. There are two basic appronches to this - one is to build a loosely-coupled system and the other is to form a tightly-coupled system [PS85].In a loosely-coupled system, the processors do not share common memory or a common clock; but sharing of important resources like data files, softwares, special hardware components etc., is possible without duplicating the resources themselves. The processing nodes may even be geographicully separated from each other and are connected through databuses, telephone/radio links, satellite, etc. Such loosely- coupled systems are …

Optimum Continuous Sampling Plans And A Few Other Sqc Problems., D Ghosh Dr.

Doctoral Theses

The wide acceptance of Statistics as a basic tool in technölogical growth, later recog- nised as a Key technology, gained ground with the pioneering work of Shewhart in 20s, introducing Statistical Quality Control (SQC) in manufacturing industry. Around the same time a solid statistical basis was being worked out for the ageold concepts of sampling inspection for industrial products. By 1930, acceptance sam- pling for lot by lot inspection was being applied in Western Electric Company and elsewhere. Since then statistical tools have been the major technical inputs of To- tal Quality Management which has spread far and wide as …

Identification Of Cutting Force In End Milling Operations Using Recurrent Neural Networks, Q. Xu, K. Krishnamurthy, Bruce M. Mcmillin, Wen Feng Lu

Mechanical and Aerospace Engineering Faculty Research & Creative Works

The problem of identifying the cutting force in end milling operations is considered in this study. Recurrent neural networks are used here and are trained using a recursive least squares training algorithm. Training results for data obtained from a SAJO 3-axis vertical milling machine for steady slot cuts are presented. The results show that a recurrent neural network can learn the functional relationship between the feed rate and steady-state average resultant cutting force very well. Furthermore, results for the Mackey-Glass time series prediction problem are presented to illustrate the faster learning capability of the neural network scheme presented here

A Recursive Least Squares Training Algorithm For Multilayer Recurrent Neural Networks, Q. Xu, K. Krishnamurthy, Bruce M. Mcmillin, Wen Feng Lu

Mechanical and Aerospace Engineering Faculty Research & Creative Works

Recurrent neural networks have the potential to perform significantly better than the commonly used feedforward neural networks due to their dynamical nature. However, they have received less attention because training algorithms/architectures have not been well developed. In this study, a recursive least squares algorithm to train recurrent neural networks with an arbitrary number of hidden layers is developed. The training algorithm is developed as an extension of the standard recursive estimation problem. Simulated results obtained for identification of the dynamics of a nonlinear dynamical system show promising results.

Knowledge-Based Nonuniform Crossover, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

We present a new "knowledge-based non-uniform crossover" (KNUX) operator for genetic algorithms (GA's) that generalizes uniform crossover. We extend this to "Dynamic KNUX" (DKNUX), which constantly updates the knowledge extracted so far from the environment's feedback on previously generated chromosomes. KNUX can improve on good solutions previously obtained by using other algorithms. The modifications made by KNUX are orthogonal to other changes in parameters of GA's, and can be pursued together with any other proposed improvements. Whereas most genetic search methods focus on improving the move-selection procedures, after having chosen a fixed move-generation mechanism, KNUX and DKNUX make the move-generation …

Multivalued Approach For Uncertainty Management., Deba Prasad Mandal Dr.

Doctoral Theses

Real life problems are rarely free from uncertainty which usually emerges from the deficiencies of information available from a situation. The defi- ciencies may result from incomplete, imprecise, not fully reliable, vague or contradictory information depending on the problem. Management of uncer- tainty in a decision making system has been an important research problem for many years.Until the inception of the concept of fuzzy set theory in 1965 (1), the theory of probability and statistics was the primary mathematical tool for modeling uncertainty in a system/situation. Fuzzy set theory has shown enormous proinise in handling uncertaintics to a reasonable extent …

The Transportation Primitive, Ravi V. Shankar, Khaled A. Alsabti, Sanjay Ranka

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

This paper presents algorithms for implementing the transportation primitive on a distributed memory parallel architecture. The transportation primitive performs many-to-many personalized communication with bounded incoming and outgoing traffic. We present a two-stage deterministic algorithm that decomposes the communication with possibly high variance in message size into two communication stages with low message size variance. If the maximum outgoing or incoming traffic at any processor is t, transportation can be done in 2t¯ time (+ lower order terms) when t O(p 2 + pø=¯) (¯ is the inverse of the data transfer rate, ø is the startup overhead). If the maximum …

Runtime Array Redistribution In Hpf Programs, Rajeev Thakur, Alok Choudhary, Geoffrey C. Fox

Northeast Parallel Architecture Center

This paper describes efficient algorithms for runtime array redistribution in HPF programs. We consider block(m) to cyclic, cyclic to block(m) and the general cyclic(x) to cyclic(y) type redistributions. We initially describe algorithms for one-dimensional arrays and then extend the methodology to multidimensional arrays. The algorithms are practical enough to be easily implemented in the runtime library of an HPF compiler and can also be directly used in application programs requiring redistribution. Performance results on the Intel Paragon are discussed.

A Numerical Study Of High-Speed Missile Configurations Using A Block- Structured Parallel Algorithm, Douglas C. Blake

Theses and Dissertations

A numerical analysis of the aerodynamic phenomena associated with the high-speed flight of a sharp-nosed, four-finned, high-fineness ratio missile using a block-structured, parallel computer algorithm is presented. The algorithm, PANS-3EM, utilizes a second-order-accurate, shock-capturing, Total Variation Diminishing scheme and incorporates a Baldwin-Lomax turbulence model. PANS-3EM allows for extreme flexibility in the choice of computational domain decomposition and computing machine of implementation. Developmental work consists of conceptualization and verification of the algorithm as well as parallel performance and scalability studies conducted on a variety of computing platforms. Using PANS-3EM, the aerodynamic characteristics of the missile are investigated. Drag and pitching moment …