Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 19 of 19
Full-Text Articles in Physical Sciences and Mathematics
An Efficient Scheme For Authenticating Public Keys In Sensor Networks, Wenliang Du, Ronghua Wang, Peng Ning
An Efficient Scheme For Authenticating Public Keys In Sensor Networks, Wenliang Du, Ronghua Wang, Peng Ning
Electrical Engineering and Computer Science - All Scholarship
With the advance of technology, Public Key Cryptography (PKC) will sooner or later be widely used in wireless sensor networks. Recently, it has been shown that the performance of some public key algorithms, such as Elliptic Curve Cryptography (ECC), is already close to being practical on sensor nodes. However, the energy consumption of PKC is still expensive, especially compared to symmetric-key algorithms. To maximize the lifetime of batteries, we should minimize the use of PKC whenever possible in sensor networks. This paper investigates how to replace one of the important PKC operations–the public key authentication–with symmetric key operations that are …
A Pairwise Key Pre-Distribution Scheme For Wireless Sensor Networks, Wenliang Kevin Du, Jing Deng, Yunghsiang S. Han, Pramod K. Varshney
A Pairwise Key Pre-Distribution Scheme For Wireless Sensor Networks, Wenliang Kevin Du, Jing Deng, Yunghsiang S. Han, Pramod K. Varshney
Electrical Engineering and Computer Science - All Scholarship
This paper, we provide a framework in which to study the security of key pre-distribution schemes, propose a new key pre-distribution scheme which substantially improves the resilience of the network compared to previous schemes, and give an in-depth analysis of our scheme in terms of network resilience and associated overhead. Our scheme exhibits a nice threshold property: when the number of compromised nodes is less than the threshold, the probability that communications between any additional nodes are compromised is close to zero. This desirable property lowers the initial payoff of smaller-scale network breaches to an adversary, and makes it necessary …
A Compiler Algorithm For Optimizing Locality In Loop Nests, Mahmut Kandemir, J. Ramanujam, Alok Choudhary
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 …
Random Number Generators For Parallel Computers, Paul D. Coddington
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 …
Unsupervised Algorithms For Learning Emergent Spatio-Temporal Correlations, Chaitanya Tumuluri
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 …
Knowledge-Based Nonuniform Crossover, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka
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 …
The Transportation Primitive, Ravi V. Shankar, Khaled A. Alsabti, Sanjay Ranka
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
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.
Genetic Algorithms For Stochastic Flow Shop No Wait Scheduling, Harpal Maini, Ubirajara R. Ferreira
Genetic Algorithms For Stochastic Flow Shop No Wait Scheduling, Harpal Maini, Ubirajara R. Ferreira
Electrical Engineering and Computer Science - Technical Reports
ln this paper we present Genetic Algorithms - evolutionary algorithms based on an analogy with natural selection and survival of the fittest - applied to an NP Complete combinatorial optimization problem: minimizing the makespan of a Stochastic Flow Shop No Wait (FSNW) schedule. This is an important optimization criteria in real-world situations and the problem itself is of practical significance. We restrict our applications to the three machine flow shop no wait problem which is known to be NP complete. The stochastic hypothesis is that the processing times of jobs are described by normally distributed random variables. We discuss how …
Numerical Solution Of Laplace's Equation, Per Brinch Hansen
Numerical Solution Of Laplace's Equation, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
This tutorial discusses Laplace's equation for steady state heat flow in a two-dimensional region with fixed temperatures on the boundaries. The equilibrium temperatures are computed for a square grid using successive overrelaxation with parity ordering of the grid elements. The numerical method is illustrated by a Pascal algorithm. We assume that the reader is familiar with elementary calculus.
Parallel Cellular Automata: A Model Program For Computational Science, Per Brinch Hansen
Parallel Cellular Automata: A Model Program For Computational Science, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
We develop a model program for parallel execution of cellular automata on a multicomputer. The model program is then adapted for simulation of forest fires and numerical solution of Laplace's equation for stationary heat flow. The performance of the parallel program is analyzed and measured on a Computing Surface configured as a matrix of transputers with distributed memory.
Multiple-Length Division Revisited: A Tour Of The Minefield, Per Brinch Hansen
Multiple-Length Division Revisited: A Tour Of The Minefield, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
Long division of natural numbers plays a crucial role in Cobol arithmetic, cryptography, and primality testing. Only a handful of textbooks discuss the theory and practice of long division, and none of them do it satisfactorily. This tutorial attempts to fill this surprising gap in the literature on computer algorithms. We illustrate the subtleties of long division by examples, define the problem concisely, summarize the theory, and develop a complete Pascal algorithm using a consistent terminology.
Simulated Annealing, Per Brinch Hansen
Simulated Annealing, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
This tutorial describes simulated annealing, an optimization method based on the principles of statistical mechanics. Simulated annealing finds near-optimal solutions to optimization problems that cannot be solved exactly because they are NP-complete. The method is illustrated by a Pascal algorithm for the traveling salesperson problem. The performance of the algorithm was measured on a Computing Surface.
Primality Testing, Per Brinch Hansen
Primality Testing, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
This tutorial describes the Miller-Rabin method for testing the primality of large integers. The method is illustrated by a Pascal algorithm. The performance of the algorithm was measured on a Computing Surface.
Designing Efficient Maximum-Likelihood Soft-Decision Decoding Algorithms For Linear Block Codes Using Algorithm A*, Yunghsiang S. Han, Carlos R.P. Hartmann
Designing Efficient Maximum-Likelihood Soft-Decision Decoding Algorithms For Linear Block Codes Using Algorithm A*, Yunghsiang S. Han, Carlos R.P. Hartmann
Electrical Engineering and Computer Science - Technical Reports
In this report we present a class of efficient maximum-likelihood soft-decision decoding algorithms for linear block codes. The approach used here is to convert the decoding problem into a search problem through a graph which is a trellis for an equivalent code of the transmitted code. Algorithm A*, which uses a priority-first search strategy, is employed to search through this graph. This search is guided by an evaluation function f defined to take advantage of the information provided by the received vector and the inherent properties of the transmitted code. This function f is used to drastically reduce the search …
A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang
A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang
Electrical Engineering and Computer Science - Technical Reports
This paper presents a simple load balancing algorithm and its probabilistic analysis. Unlike most of the previous load balancing algorithms, this algorithm maintains locality. We show that the cost of this load balancing algorithm is small for practical situations and discuss some interesting applications for data remapping.
Scheduling Regular And Irregular Communication Patterns On The Cm-5, Ravi Ponnusamy, Rajeev Thakur, Alok Choudhary, Geoffrey C. Fox
Scheduling Regular And Irregular Communication Patterns On The Cm-5, Ravi Ponnusamy, Rajeev Thakur, Alok Choudhary, Geoffrey C. Fox
Northeast Parallel Architecture Center
In this paper, we study the communication characteristics of the CM-5 and the performance effects of scheduling regular and irregular communication patterns on the CM-5. We consider the scheduling of regular communication patterns such as complete exchange and broadcast. We have implemented four algorithms for complete exchange and studied their performances on a 2D FFT algorithm. We have also implemented four algorithms for scheduling irregular communication patterns and studied their performance on the communication patterns of several synthetic as well as real problems such as the conjugate gradient solver and the Euler solver.
The Fast Fourier Transform, Per Brinch Hansen
The Fast Fourier Transform, Per Brinch Hansen
Electrical Engineering and Computer Science - Technical Reports
This tutorial discusses the fast Fourier transform, which has numerous applications in signal and image processing. The FFT computes the frequency components of a signal that has been sampled at n points in O( n log n) time. We explain the FFT and illustrate it by examples and Pascal algorithms. We assume that you are familiar with elementary calculus.
Three--Dimensional Medical Imaging: Algorithms And Computer Systems, M. R. Stytz, G. Frieder, O. Frieder
Three--Dimensional Medical Imaging: Algorithms And Computer Systems, M. R. Stytz, G. Frieder, O. Frieder
College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects
This paper presents an introduction to the field of three-dimensional medical imaging It presents medical imaging terms and concepts, summarizes the basic operations performed in three-dimensional medical imaging, and describes sample algorithms for accomplishing these operations. The paper contains a synopsis of the architectures and algorithms used in eight machines to render three-dimensional medical images, with particular emphasis paid to their distinctive contributions. It compares the performance of the machines along several dimensions, including image resolution, elapsed time to form an image, imaging algorithms used in the machine, and the degree of parallelism used in the architecture. The paper concludes …