Computer Sciences Commons^™

Studies Of Qcd In E+E- → Hadrons At Ecm = 130 And 136 Gev, D. Buskulic, M. Thulasidas

Research Collection School Of Computing and Information Systems

Studies of QCD in e+e−→e+e−→ Hadrons at Ecm=Ecm=} 130 and 136 GeV The ALEPH Collaboration An analysis of the properties of hadronic final states produced in electron-positron annihilation at centre-of-mass energies of 130 and 136 GeV is presented. The measurements are based on a data sample of 5.7 pb−1pb−1 collected in November 1995 with the \Aleph detector at LEP. Inclusive charged particle distributions, jet rates and event-shape distributions are measured and the results are compared with the predictions of QCD-based models. From the measured distributions quantities are determined for which the dependence on the centre-of-mass energy can be predicted by …

Least Space-Time First Scheduling Algorithm : Scheduling Complex Tasks With Hard Deadline On Parallel Machines, Bo-Chao Cheng

Dissertations

Both time constraints and logical correctness are essential to real-time systems and failure to specify and observe a time constraint may result in disaster. Two orthogonal issues arise in the design and analysis of real-time systems: one is the specification of the system, and the semantic model describing the properties of real-time programs; the other is the scheduling and allocation of resources that may be shared by real-time program modules.

The problem of scheduling tasks with precedence and timing constraints onto a set of processors in a way that minimizes maximum tardiness is here considered. A new scheduling heuristic, Least …

Safe Code Transfromations For Speculative Execution In Real-Time Systems, Mohamed Mohamed Younis

Dissertations

Although compiler optimization techniques are standard and successful in non-real-time systems, if naively applied, they can destroy safety guarantees and deadlines in hard real-time systems. For this reason, real-time systems developers have tended to avoid automatic compiler optimization of their code. However, real-time applications in several areas have been growing substantially in size and complexity in recent years. This size and complexity makes it impossible for real-time programmers to write optimal code, and consequently indicates a need for compiler optimization. Recently researchers have developed or modified analyses and transformations to improve performance without degrading worst-case execution times. Moreover, these optimization …

Massively Parallel Reasoning In Transitive Relationship Hierarchies, Yugyung Lee

Dissertations

This research focuses on building a parallel knowledge representation and reasoning system for the purpose of making progress in realizing human-like intelligence. To achieve human-like intelligence, it is necessary to model human reasoning processes by programs. Knowledge in the real world is huge in size, complex in structure, and is also constantly changing even in limited domains. Unfortunately, reasoning algorithms are very often intractable, which means that they are too slow for any practical applications. One technique to deal with this problem is to design special-purpose reasoners. Many past Al systems have worked rather nicely for limited problem sizes, but …

Application Of Geometric Hashing Techniques To Retrieval Of High Dimensional Objects In Scientific Databases, Joyce Ye Lu

Theses

An approach to designing very fast algorithms for tackling the problem of approximate object matching in very large databases of high-dimensional objects is proposed. Given are a target object C and a database D containing information about a set of high-dimensional objects each of which is represented as a set of points. Our algorithms have an off-line object preprocessing (shape representation) phase and a recognition phase. The described algorithms determine those objects from D which are the closest to object C, according to delete or insert some points, move and rotation. All of these can be achieved very efficiently with …

Abstraction Of An Object-Oriented Vocabulary By Providing A Standardized Interface, Hemant Kothavade

Theses

Controlled vocabularies are ubiquitous in varied application fields. They are particularly helpful in the medical field since they can unify disparate terminologies and provide information in a compact, comprehensible manner. In this thesis, we present a mechanism to efficiently retrieve and update knowledge stored in a controlled vocabulary modeled as an Object-Oriented Database (OODB) system. We aim to provide a standardized interface to the vocabulary, such that the implementation details of the vocabulary are transparent to all users. The user of this standardized interface will typically be an application programmer who is trying to provide the vocabulary's knowledge-base to end …

Automated Parallelization Of Discrete State-Space Generation, David M. Nicol, Gianfranco Ciardo

Computer Science Technical Reports

We consider the problem of generating a large state-space in a distributed fashion. Unlike previously proposed solutions that partition the set of reachable states according to a hashing function provided by the user, we explore heuristic methods that completely automate the process. The first step is an initial random walk through the state space to initialize a search tree, duplicated in each processor. Then, the reachability graph is built in a distributed way, using the search tree to assign each newly found state to classes assigned to the available processors. Furthermore, we explore two remapping criteria that attempt to balance …

Structural Issues In Active Rule Systems, James Bailey, Guozhu Dong, Kotagiri Ramamohanarao

Kno.e.sis Publications

Active database systems enhance the functionality of traditional databases through the use of active rules or ‘triggers’. There is little consensus, though, on what components should be included in a rule system. In this paper, the expressive power of some simple active database rule systems is examined and the effect of choosing different features studied. Four important parameters of variation are presented, namely the rule language, the external query language, the meta rule language and the pending rule structure. We show that each of these is highly influential in determining the expressiveness of the rule system as a whole, and …

An Error Handling Framework For The Orbwork Workflow Enactment Service Of Meteor, Davasish Worah, Amit P. Sheth, Krzysztof J. Kochut, John A. Miller

Kno.e.sis Publications

Workflow Management Systems (WFMSs) can be used to re-engineer, streamline, automate, and track organizational processes involving humans and automated information systems. However, the state-of-the-art in workflow technology suffers from a number of limitations that prevent it from being widely used in large-scale mission critical applications. Error handling is one such issue. What makes the task of error handling challenging is the need to deal with errors that appear in various components of a complex distributed application execution environment, including various WFMS components, workflow application tasks of different types, and the heterogeneous computing infrastructure.

In this paper, we discuss a top-down …

Incorporating A Connectionist Vision Module Into A Fuzzy, Behavior-Based Robot Controller, Doug Blank, J. Oliver Ross

Computer Science Faculty Research and Scholarship

This paper describes the initial steps required to incorporate an artificial neural network vision module into an established fuzzy logic, behavior-based mobile robot and controller. This efficient and robust method is demonstrated to show its effectiveness in simple real-world environments.

A One-Pass Algorithm For Accurately Estimating Quantiles For Disk-Resident Data, Khaled Alsabti, Sanjay Ranka, Vineet Singh

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

The '-quantile of an ordered sequence of data values is the element with rank ' \Theta n, where n is the total number of values. Accurate estimates of quantiles are required for the solution of many practical applications. In this paper, we present a new algorithm for estimating the quantile values for disk-resident data. Our algorithm has the following characteristics: (1) It requires only one pass over the data; (2) It is deterministic; (3) It produces good lower and upper bounds of the true values of the quantiles; (4) It requires no a priori knowledge of the distribution of the …

Semantics Vs. Syntax Vs. Computations: Machine Models For Type-2 Polynomial-Time Bounded Functionals, James S. Royer

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

This paper investigates analogs of the Kreisel-Lacombe-Shoenfield Theorem in the context of the type-2 basic feasible functionals. We develop a direct, polynomial-time analog of effective operation in which the time bounding on computations is modeled after Kapron and Cook's scheme for their basic polynomial-time functionals. We show that if P = NP, these polynomial-time effective operations are strictly more powerful on R (the class of recursive functions) than the basic feasible functions. We also consider a weaker notion of polynomial-time effective operation where the machines computing these functionals have access to the computations of their procedural parameter, but not to …

Concurrent Simulation Of Plasma Reactors, Marc Rieffel, Stephen Taylor, Jerrell Watts, Sadasivan Shankar

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

This paper summarizes the computational techniques behind a novel concurrent simulation method used for studying the neutral flow inside plasma reactors. The technique is intended to cope with low pressure flow (less than 1.5 Torr) in realistic three-dimensional geometries. It is based on the Direct Simulation Monte Carlo method to accurately model rarefied gas flow. The concurrent formulation operates on a broad variety of shared-memory multiprocessors, multicomputers, and networked workstations.

Practical Algorithms For Selection On Coarse-Grained Parallel Computers, Ibraheem Al-Furaih, Srinivas Aluru, Sanjay Goil, Sanjay Ranka

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

In this paper, we consider the problem of selection on coarse-grained distributed memory parallel computers. We discuss several deterministic and randomized algorithms for parallel selection. We also consider several algorithms for load balancing needed to keep a balanced distribution of data across processors during the execution of the selection algorithms. We have carried out detailed implementations of all the algorithms discussed on the CM-5 and report on the experimental results. We demonstrate that the randomized algorithms are superior to their deterministic counterparts.

Integer Sorting Algorithms For Coarse-Grained Parallel Machines, Khaled Alsabti, Sanjay Ranka

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

Integer sorting is a subclass of the sorting problem where the elements have integer values and the largest element is polynomially bounded in the number of elements to be sorted. It is useful for applications in which the size of the maximum value of element to be sorted is bounded. In this paper, we present a new distributed radix-sort algorithm for integer sorting. The structure of our algorithm is similar to radix sort except that it typically requires less number of communication phases. We present experimental results for our algorithm on two distributed memory multiprocessors, the Intel Paragon and the …

The Software Architecture Of A Virtual Distributed Computing Environment, Haluk Topcuoglu, Salim Hariri, Wojtek Furmanski, Jon Valente

Electrical Engineering and Computer Science - All Scholarship

The requirements of grand challenge problems and the deployment of gigabit networks makes the network computing framework an attractive and cost effective computing environment with which to interconnect geographically distributed processing and storage resources. Our project, Virtual Distributed Computing Environment (VDCE), provides a problem-solving environment for high-performance distributed computing over wide area networks. VDCE delivers well-defined library functions that relieve end-users of tedious task implementations and also support reusability. In this paper we present the conceptual design of VDCE software architecture, which is defined in three modules: a) the Application Editor, a user-friendly application development environment that generates the Application …

Parallel Domain Decomposition And Load Balancing Using Space-Filling Curves, Srinivas Aluru, Faith E. Sevilgen

Electrical Engineering and Computer Science - All Scholarship

Partitioning techniques based on space-filling curves have received much recent attention due to their low running time and good load balance characteristics. The basic idea underlying these methods is to order the multidimensional data according to a space-filling curve and partition the resulting one-dimensional order. However, space-filling curves are defined for points that lie on a uniform grid of a particular resolution. It is typically assumed that the coordinates of the points are representable using a fixed number of bits, and the run-times of the algorithms depend upon the number of bits used. In this paper, we present a simple …

Selective Crossover: Towards Fitter Offspring, Chilukuri K. Mohan

Electrical Engineering and Computer Science - All Scholarship

A new general-purpose crossover operator is proposed. The representation of a candidate solution is slightly perturbed, and the ensuing changes in fitness are calculated. Such fitness changes (for parents) are used in constructing the offspring resulting from crossover. Experiments with several sets of problems demonstrate that this approach leads to rapid increases in average and best fitness, and performs much better than traditional general-purpose crossover operators.

A Global Computing Environment For Networked Resources, Haluk Topcuoglu, Salim Hariri

Electrical Engineering and Computer Science - All Scholarship

Current advances in high-speed networks and WWW technologies have made network computing a cost-effective, high-performance computing alternative. New software tools are being developed to utilize efficiently the network computing environment. Our project, called Virtual Distributed Computing Environment (VDCE), is a high-performance computing environment that allows users to write and evaluate networked applications for different hardware and software configurations using a web interface. In this paper we present the software architecture of VDCE by emphasizing application development and specification, scheduling, and execution/runtime aspects.

Simulated Annealing And Genetic Algorithms For Partial Shape Matching, Ender Ozcan, Chilukuri K. Mohan

Electrical Engineering and Computer Science - All Scholarship

Partial shape matching may be viewed as an optimization problem, to be solved using methods such as simulated annealing (SA) and genetic algorithms (GAs). We apply and compare both these methods for matching input shapes with model shapes described in terms of features such as line segments and angles. The quality of matching is gauged using a measure derived from attributed shape grammars [10, 11]. Current results show that both SA and GA succeed in the shape matching task; the GA is faster and yields the global optimum more often than the versions of SA implemented.

Topology And Logic Programming Semantics, Pascal Hitzler

Computer Science and Engineering Faculty Publications

Logic programming employs logic as a programming language. Thus a logic program consists of a set of clauses of a certain form most often a subset of the clauses of first order logic viewed as axioms. Computation in this paradigm is deduction from these axioms via some interpreter.

Logic programming semantics is concerned with background theory for logic programming. It tries to provide models for logic programs to give them their intended meaning and to connect them with practically implementable interpreters.

The Use Of Prime Numbers As An Effective Method Of Cryptology, Joshua Flynn

Honors Theses, 1963-2015

With the increasing amount of information transmitted over networks, there is a need to be able to keep this information from falling into the wrong hands. The method that has been used for the past couple of decades is that of cryptography. This paper gives an explanation of cryptography, as well as different alogorithms that are used to solve the problem. One unique thing about a couple of the algorithms is that they use properties provided by prime numbers. In particular, the RSA model, invented by Rivest, Shamir and Adelman, is one model which utilizes the theory that it is …

Experiments With "Hp Java", Bryan Carpenter, Yuh-Jye Chang, Geoffrey C. Fox, Donald Leskiw

Northeast Parallel Architecture Center

We consider the possible role of Java as a language for High Performance Computing. After discussing reasons why Java may be a natural candidate for a portable parallel programming language, we describe several case studies. These cover Java socket programming, message-passing through a Java interface to MPI, and class libraries for data-parallel programming in Java.

Hpjava: Data Parallel Extensions To Java, Bryan Carpenter, Guansong Zhang, Geoffrey C. Fox, Xinying Li

Northeast Parallel Architecture Center

We outline an extension of Java for programming with distributed arrays. The basic programming style is Single Program Multiple Data (SPMD), but parallel arrays are provided as new language primitives. Further extensions include three distributed control constructs, the most important being a data-parallel loop construct. Communications involving distributed arrays are handled through a standard library of collective operations. Because the underlying programming model is SPMD programming, direct calls to MPI or other communication packages are also allowed in an HPJava program.

How Secure Transactions Are Achieved On The Internet Using Ssl: An Honors Presentation Of Internet Security Practices And Protocols, Julie Klinefelter

Honors Theses, 1963-2015

The goal of this project is to research and present the security protocol "Secure Sockets Layer" or as it is more commonly referred to, "SSL." SSL is one of the main encryption techniques used by the internet industry to help ensure the secure transfer of information across the internet. It is one of the main encryption techniques currently under review by Internet Engineering Task Force. SSL is comprised of a strict protocol that initiates a secure "session" between two computing devices. The session is established above the transport level (on the OSI model) and encrypts from the session up. Therefore …

A Comparison Of Annealing Techniques For Academic Course Scheduling, M.A. Saleh Elmohamed, Geoffrey C. Fox, Paul Coddington

Northeast Parallel Architecture Center

In this study we have tackled the NP-hard problem of academic class scheduling (or timetabling) at the university level. We have investigated a variety of approaches based on simulated annealing, including mean-field annealing, simulated annealing with three different cooling schedules, and the use of a rule-based preprocessor to provide a good initial solution for annealing. The best results were obtained using simulated annealing with adaptive cooling and reheating as a function of cost, and a rule-based preprocessor. This approach enabled us to obtain valid schedules for the timetabling problem for a large university, using a complex cost function that includes …

A Load Balancing Technique For Multiphase Computations, Jerrell Watts, Marc Rieffel, Stephen Taylor

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

Parallel computations comprised of multiple, tightly interwoven phases of computation may require a different approach to dynamic load balancing than single-phase computations. This paper presents a load sharing method based on the view of load as a vector, rather than as a scalar. This approach allows multiphase computations to achieve higher efficiency on large-scale multicomputers than possible with traditional techniques. Results are presented for two large-scale particle simulations running on 128 nodes of an Intel Paragon and on 256 processors of a Cray T3D, respectively.

Standardization Of A Communication Middleware For High-Performance Real-Time Systems, Arkady Kanevsky, Anthony Skjellum, Jerrell Watts

Electrical Engineering and Computer Science - All Scholarship

The last several years saw an emergence of standardization activities for real-time systems including standardization of operating systems (series of POSIX standards [1]), of communication for distributed (POSIX.21 [10]) and parallel systems (MPI/RT [5]) and real-time object management (realtime CORBA [9]). This article describes the ongoing standardization work and implementation of communication middleware for high performance real-time computing. The real-time message passing interface (MPI/RT) advances the non-real-time high-performance communication standard Message Passing Interface Standard (MPI), emphasizing changes that enable and support real-time communication, and is targeted for embedded, fault-tolerant and other real-time systems. MPI/RT is the only communication middleware layer …

Resource Access Control For An Internet User Agent, Nataraj Nagaratnam, Steven B. Byrne

Electrical Engineering and Computer Science - All Scholarship

The rapid increase in the Internet's connectivity has lead to proportional increase in the development of Web-based applications. Usage of downloadable content has proved effective in a number of emerging applications including electronic commerce, software components on-demand, and collaborative systems. In all these cases, Internet user agents (like browsers, tuners) are widely used by the clients to utilize and execute such downloadable content. With this new technology of using downloadable content comes the problem of the downloaded content obtaining unauthorized access to the client's resources. In effect, granting a hostile remote principal the requested access to client's resources may lead …

Random Walks On Wheels, Matthew Lee, Mark Stamp

Faculty Publications, Computer Science

Suppose two particles occupy distinct vertices of a wheel graph and at each step the two particles move independently to adjacent vertices. In this paper we find the expected number of moves until the particles land on the same vertex.