Open Access. Powered by Scholars. Published by Universities.®

Computer Sciences Commons™

Open Access. Powered by Scholars. Published by Universities.®

Syracuse University

Discipline
Keyword
Publication Year
Publication
Publication Type

Articles 421 - 450 of 532

Full-Text Articles in Computer Sciences

Semi-Distributed Load Balancing For Massively Parallel Multicomputer Systems, Ishfaq Ahmad, Arif Ghafoor Aug 1991

Semi-Distributed Load Balancing For Massively Parallel Multicomputer Systems, Ishfaq Ahmad, Arif Ghafoor

Electrical Engineering and Computer Science - Technical Reports

This paper presents a semi-distributed approach, for load balancing in large parallel and distributed systems, which is different from the conventional centralized and fully distributed approaches. The proposed strategy uses a two-level hierarchical control by partitioning the interconnection structure of a distributed or multiprocessor system into independent symmetric regions (spheres) centered at some control points. The central points, called schedulers, optimally schedule tasks within their spheres and maintain state information with low overhead. We consider interconnection structures belonging to a number of families of distance transitive graphs for evaluation, and using their algebraic characteristics, show that identification of spheres and …

Go to article

Explicit Clock Temporal Logic In Timing Constraints For Real-Time Systems, S. Ramanna, J. F. Peters Iii Aug 1991

Explicit Clock Temporal Logic In Timing Constraints For Real-Time Systems, S. Ramanna, J. F. Peters Iii

Electrical Engineering and Computer Science - Technical Reports

A form of explicit clock temporal logic (called TLrt) useful in specifying timing constraints on controller actions, a real-time database (rtdb) items, and constraints in a real-time constraint base (rtcb), is presented. Timing as well as other forms of constraints are stored in the rtcb. A knowledge-based approach to ensure the integrity of information in an rtdb is given. The rtcb is realized as a logic program called Constrainer, which is a historyless integrity checker for a real-time database. The consistency and integrity issues for an rtcb and rtdb are investigated. The formal bases for a temporally complete rtdb and …

Go to article

The Complexity Of Local Stratification, Peter Cholak, Howard A. Blair Jul 1991

The Complexity Of Local Stratification, Peter Cholak, Howard A. Blair

Electrical Engineering and Computer Science - Technical Reports

The class of locally stratified logic programs is shown to be Π11-complete by the construction of a reducibility of the class of infinitely branching nondeterministic finite register machines.nondeterministic finite register machines.

Go to article

Fault-Tolerant Load Management For Real-Time Distributed Computer Systems, Arif Ghafoor, Ishfaq Ahmad Jul 1991

Fault-Tolerant Load Management For Real-Time Distributed Computer Systems, Arif Ghafoor, Ishfaq Ahmad

Electrical Engineering and Computer Science - Technical Reports

This paper presents a fault-tolerant scheme applicable to any decentralized load balancing algorithms used in soft real-time distributed systems. Using the theory of distance-transitive graphs for representing topologies of these systems, the proposed strategy partitions these systems into independent symmetric regions (spheres) centered at some control points. These central points, called fault-control points, provide a two-level task redundancy and efficiently re-distribute the load of failed nodes within their spheres. Using the algebraic characteristics of these topologies, it is shown that the identification of spheres and fault-control points is, in general, is an NP-complete problem. An efficient solution for this problem …

Go to article

Nonlinear System Identification Using Recurrent Networks, Hyungkeun Lee, Y. Park, Kishan Mehrotra, Sanjay Ranka Jul 1991

Nonlinear System Identification Using Recurrent Networks, Hyungkeun Lee, Y. Park, Kishan Mehrotra, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

This paper presents empirical results on the application of neural networks to system identification and inverse system identification. Recurrent and Feedforward network models are used to build an emulator of a simple nonlinear gantry crane system, and for the inverse dynamics of the system. Recurrent networks were observed to perform slightly better than feedforward networks for these problems.

Go to article

Constructing Real-Time Systems From Temporal I/O Automata, J. F. Peters Iii, S. Ramanna Jul 1991

Constructing Real-Time Systems From Temporal I/O Automata, J. F. Peters Iii, S. Ramanna

Electrical Engineering and Computer Science - Technical Reports

A new class of communicating automata called Temporal Input/Output Automata (TAi/os) is introduced. A TAi/o is a predicate automaton used to specify real-time systems. The specification provided by a TAi/o includes state predicates with proof expressions and abstract program syntax as attributes. An abstract program is extracted during a constructive proof of the specification using the proof expressions. A TAi/o specification also includes hard, real-time constraints on program behavior. The predictability of deterministic, temporally complete TAi/o is investigated. The formulation of real-time system transductions and transduction rules for TAi/os in explicit clock temporal logic is given. An illustration of the …

Go to article

A Generic Multiplication Pipeline, Per Brinch Hansen Jul 1991

A Generic Multiplication Pipeline, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This paper illustrates the benefits of developing generic algorithms for parallel programming paradigms which can be adapted to different applications. We consider a combinatorial problem called tuple multiplication. This paradigm includes matrix multiplication and the all-pairs shortest paths problem as special cases. We develop a generic pipeline for tuple multiplication. From the generic algorithm we derive pipelines for matrix multiplication and shortest paths computation by making substitutions of data types and functions. The performance of the matrix multiplication pipeline is analyzed and measured on a Computing Surface.

Go to article

A Sixteen-Valued Algorithm For Test Generation In Combinational Circuits, Akhtar Uz Zaman, M. Ali, Carlos R.P. Hartmann Jun 1991

A Sixteen-Valued Algorithm For Test Generation In Combinational Circuits, Akhtar Uz Zaman, M. Ali, Carlos R.P. Hartmann

Electrical Engineering and Computer Science - Technical Reports

A 16-valued logic system for testing combinational circuits is presented. This logic system has been used to develop SIMPLE, an efficient test generation algorithm for single stuck-at faults. The proposed scheme for testing stuck-at faults is based on imposing all the constraints that must be satisfied in order to sensitize a path from a fault site to a primary output. Consequently all deterministic implications are fully considered prior to the enumeration process. The resulting ability to identify inconsistencies prior to enumeration improves the possibility of quicker identification of redundant faults. In order to prune the search space we have introduced …

Go to article

A Variable-Free Logic For Mass Terms, William C. Purdy Jun 1991

A Variable-Free Logic For Mass Terms, William C. Purdy

Electrical Engineering and Computer Science - Technical Reports

This paper presents a logic appropriate for mass terms, that is, a logic that does not presuppose interpretation in discrete models. Models may range from atomistic to atomless. This logic is a generalization of the author's work on natural language reasoning. The following claims are made for this logic. First, absence of variables makes it simpler than more conventional formalizations based on predicate logic. Second, capability to deal effectively with discrete terms, and in particular with singular terms, can be added to the logic, making it possible to reason about discrete entities and mass entities in a uniform manner. Third, …

Go to article

An Evolutionary Approach To Load Balancing Parallel Computations, N. Mansouri, Geoffrey C. Fox Apr 1991

An Evolutionary Approach To Load Balancing Parallel Computations, N. Mansouri, Geoffrey C. Fox

Electrical Engineering and Computer Science - Technical Reports

We present a new approach to balancing the workload in a multicomputer when the problem is decomposed into subproblems mapped to the processors. It is based on a hybrid genetic algorithm. A number of design choices for genetic algorithms are combined in order to ameliorate the problem of premature convergence that is often encountered in the implementation of classical genetic algorithms. The algorithm is hybridized by including a hill climbing procedure which significantly improves the efficiency of the evolution. Moreover, it makes use of problem specific information to evade some computational costs and to reinforce favorable aspects of the genetic …

Go to article

Prediction Criteria For Successful Weaning From Respiratory Support: Statistical And Connectionist Analyses, K. Ashutosh, Hyungkeun Lee, Chilukuri K. Mohan, Sanjay Ranka, Kishan Mehrotra, C. Alexander Apr 1991

Prediction Criteria For Successful Weaning From Respiratory Support: Statistical And Connectionist Analyses, K. Ashutosh, Hyungkeun Lee, Chilukuri K. Mohan, Sanjay Ranka, Kishan Mehrotra, C. Alexander

Electrical Engineering and Computer Science - Technical Reports

Objective: To develop predictive criteria for successful weaning from mechanical assistance to ventilation based upon simple clinical tests using discriminant analyses and neural network systems. Design: Retrospective development of predictive criteria and subsequent prospective testing of the same. Setting: Medical intensive care unit of a 300-bed teaching veterans administration hospital. Patients: Twenty-five ventilator-dependent elderly patients with acute respiratory failure. Interventions: Routine measurements of negative inspiratory force (NIF), tidal values (VT), minute ventilation (VE), respiratory rate (RR), vital capacity (FVC), and maximum voluntary ventilation (MVV), followed by weaning trial. Success or failure in 21 efforts analyzed by linear and quadratic discriminant …

Go to article

Performance Prediction For Distributed Load Balancing In Multicomputer Systems, Ishfaq Ahmad, Arif Ghafoor, Kishan Mehrotra Apr 1991

Performance Prediction For Distributed Load Balancing In Multicomputer Systems, Ishfaq Ahmad, Arif Ghafoor, Kishan Mehrotra

Electrical Engineering and Computer Science - Technical Reports

Computing literature has being flooded recently with a plethora of dynamic load balancing strategies for multicomputer systems. The diversity of many strategies and their dependence on a number of parameters has made it difficult to compare their effectiveness on a unified basis. Not only does each strategy consider a different environment, but the simplified assumptions obscure the relative merits and demerits of each strategy. This paper presents a solution to compare different load balancing schemes on a unified basis. Our approach, which is an integration of simulation, statistical and analytical experiments, takes into account the fundamental system parameters that can …

Go to article

A Unified Framework For Three-Valued Semantical Treatments Of Logic Programming, Feng Yang Mar 1991

A Unified Framework For Three-Valued Semantical Treatments Of Logic Programming, Feng Yang

Electrical Engineering and Computer Science - Technical Reports

Based on Fiting's Φ operator a unified framework for three-valued semantics of logic programming is presented. The truth space used in the framework is the class of partial interpretations. Underlying the truth space is two partial orderings, knowledge ordering and truth ordering. It turns out that the truth space with the truth ordering is a complete lattice and the truth space with knowledge ordering is a semi-complete lattice. Φ is proved to be continuous over the complete lattice and monotonic over the semi-complete lattice. With the use of Φ operator two well-known three-valued semantics for logic programming, Fitting's three-valued semantics …

Go to article

A Study Of Approximating The Moments Of The Job Completion Time In Pert Networks, Kishan Mehrotra, John Chai, Sharma Pillutla Mar 1991

A Study Of Approximating The Moments Of The Job Completion Time In Pert Networks, Kishan Mehrotra, John Chai, Sharma Pillutla

Electrical Engineering and Computer Science - Technical Reports

The importance of proper management of projects has not gone unrecognized in industry and academia. Consequently tools like Critical Path Method (CPM) and Program Evaluation Review Technique (PERT) for project planning have been the focus of attention of both practitioners and researchers. Determination of the Time to Complete the Job (TCJ) in PERT networks is important for planning and bidding purposes. The complexity involved in accurately determining the TCJ has led to the development of many approximating procedures. Most of them ignore the dependence between paths in the network. We propose an approximation to determine the TCJ which explicitly recognizes …

Go to article

Duality In Logic Programming, Feng Yang Mar 1991

Duality In Logic Programming, Feng Yang

Electrical Engineering and Computer Science - Technical Reports

Various approximations of classic negation have been proposed for logic programming. But the semantics for those approximations are not entirely clear. In this paper a proof-theoretic operator, we call it failure operator, denoted as FP, is associated with each logic program to characterize the meaning of various negations in logic programming. It is shown that the failure operator FP is a dual of the TP, immediate consequence operator developed by Van Emden and Kowalski and is downward continuous. It has the desirable properties entirely analogous to what TP has such as continuity, having a unique least fixpoint and a unique …

Go to article

The N-Body Pipeline, Per Brinch Hansen Mar 1991

The N-Body Pipeline, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

A general pipeline for all-pairs computations is adapted for direct force summation of n bodies which interact through gravitation only. To achieve approximate load balance the pipeline is folded several times across an array of processors. The performance of the pipeline is analyzed and measured on a Computing Surface.

Go to article

A Practical Hierarchial Model Of Parallel Computation: The Model, Todd Heywood, Sanjay Ranka Feb 1991

A Practical Hierarchial Model Of Parallel Computation: The Model, Todd Heywood, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

We introduce a model of parallel computation that retains the ideal properties of the PRAM by using it as a sub-model, while simultaneously being more reflective of realistic parallel architectures by accounting for and providing abstract control over communication and synchronization costs. The Hierarchical PRAM (H-PRAM) model controls conceptual complexity in the face of asynchrony in two ways. First, by providing the simplifying assumption of synchronization to the design of algorithms, but allowing the algorithms to work asynchronously with each other; and organizing this "control asynchrony" via an implicit hierarchy relation. Second, by allowing the restriction of "communication asynchrony" in …

Go to article

Analyzing Images Containing Multiple Sparse Patterns With Neural Networks, Rangachari Anand, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka Jan 1991

Analyzing Images Containing Multiple Sparse Patterns With Neural Networks, Rangachari Anand, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

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

We have addressed the problem of analyzing images containing multiple sparse overlapped patterns. This problem arises naturally when analyzing the composition of organic macromolecules using data gathered from their NMR spectra. Using a neural network approach, we have obtained excellent results in using NMR data to analyze the presence of various amino acids in protein molecules. We have achieved high correct classification percentages (about 87%) for images containing as many as five substantially distorted overlapping patterns.

Go to article

Scatter Scheduling For Problems With Unpredictable Structures, Min-You Wu, Wei Shu Jan 1991

Scatter Scheduling For Problems With Unpredictable Structures, Min-You Wu, Wei Shu

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

An extended scatter scheduling was applied to problems with unpredictable, asynchronous structures. It has been found that with this simple scheduling strategy, good load balance can be reached without incurring much runtime overhead. This scheduling algorithm has been implemented on hypercube machines, and its performance is compared with other scheduling strategies.

Go to article

Performance Prediction For Distributed Load Balancing On Multicomputer Systems, Ishfaq Ahmed, Arif Ghafoor, Kishan Mehrotra Jan 1991

Performance Prediction For Distributed Load Balancing On Multicomputer Systems, Ishfaq Ahmed, Arif Ghafoor, Kishan Mehrotra

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

This paper presents a performance evaluation approach to compare different distributed load balancing schemes on a unified basis. This approach is an integration of simulation, statistical and analytical models, and takes into account the fundamental system parameters that can possibly affect the performance. We show that all the sender-initiated distributed load balancing strategies can be modeled by a central server open queuing network. Furthermore, these load balancing strategies can be characterized by only two queuing parameters – the average execution queue length and the probability that a newly arrived task is executed locally or migrated to another node. To capture …

Go to article

Three--Dimensional Medical Imaging: Algorithms And Computer Systems, M. R. Stytz, G. Frieder, O. Frieder Jan 1991

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 …

Go to article

Optimal Parallel Lexicographic Sorting Using A Fine-Grained Decomposition, Ramachandran Vaidyanathan, Carlos R.P. Hartmann, Pramod Varshney Jan 1991

Optimal Parallel Lexicographic Sorting Using A Fine-Grained Decomposition, Ramachandran Vaidyanathan, Carlos R.P. Hartmann, Pramod Varshney

Electrical Engineering and Computer Science - Technical Reports

Though non-comparison based sorting techniques like radix sorting can be done with less "work" than conventional comparison-based methods, they are not used for long keys. This is because even though parallel radix sorting algorithms process the keys in parallel, the symbols in the keys are processed sequentially. In this report, we give an optimal algorithm for lexicographic sorting that can be used to sort n m-bit keys on an EREW model in Ө (log nlogm) time with Ө (mn) "work". This algorithm is not only as fast as any optimal non-comparison based algorithm, but can also be executed with less …

Go to article

Average Dependence And Random Oracles (Preliminary Report), Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer Jan 1991

Average Dependence And Random Oracles (Preliminary Report), Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

Electrical Engineering and Computer Science - Technical Reports

This paper is a technical investigation of issues in computational complexity theory relative to a random oracle. We introduce “average dependence,” an alternative method to Bennett and Gill’s “measure preserving map" technique and illustrate our technique by the following results.

Go to article

A Decentralized Task Scheduling Algorithm And Its Performance Modeling For Computer Networks, Ishfaq Ahmad, Arif Ghafoor, Kishan Mehrotra Jan 1991

A Decentralized Task Scheduling Algorithm And Its Performance Modeling For Computer Networks, Ishfaq Ahmad, Arif Ghafoor, Kishan Mehrotra

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

A dynamic task scheduling algorithm, that is stable, de-centralized, and adaptive to network topology, is presented. The proposed algorithm is an extension of nearest neighbor load balancing strategy with an enhanced degree of efficiency and it is intended for multicomputers connected by a store and forward communication network. The proposed algorithm is modeled by a central server open queuing network. It is shown that the response time of a task consists of two parts. The first part comprises a task‘s settling time which consists of scheduling time, communication time, and waiting time in scheduling and communication queues. The second part …

Go to article

Intelligent Structural Operators For The K-Way Graph Partitioning Problem, Gregor Von Laszewski Jan 1991

Intelligent Structural Operators For The K-Way Graph Partitioning Problem, Gregor Von Laszewski

Northeast Parallel Architecture Center

A parallel genetic algorithm for the graph partitioning problem is presented, which combines general heuristic algorithms with techniques that are described in evolution theory. In the parallel genetic algorithm the selection of a mate is restricted to a local neighborhood. In addition, the parallel genetic algorithm executes an adaptation step after an individual is generated, with the genetic operators crossover and mutation. During the adaptation step the solution is improved by a common algorithm. Another selection step decides if the adapted descendant should replace the parent individual. Instead of using a uniform crossover operator a more intelligent crossover operator, which …

Go to article

Optimal Processor Assignment For Pipeline Computations, David Nicol, Rahul Simha, Alok N. Choudhury, Bhagirath Narahari Jan 1991

Optimal Processor Assignment For Pipeline Computations, David Nicol, Rahul Simha, Alok N. Choudhury, Bhagirath Narahari

Electrical Engineering and Computer Science - All Scholarship

The availability of large-scale multitasked parallel architectures introduces the following processor assignment problem for pipelined computations. Given a set of tasks and their precedence constraints, along with their experimentally determined individual response times for different processor sizes, find an assignment of processors to tasks. Two objectives interest us: minimal response given a throughput requirement, and maximal throughput given a response time requirement. These assignment problems differ considerably from the classical mapping problem in which several tasks share a processor; instead, we assume that a large number of processors are to be assigned to a relatively small number of tasks. In …

Go to article

Fitting Semantics For Conditional Term Rewriting, Chilukuri K. Mohan Dec 1990

Fitting Semantics For Conditional Term Rewriting, Chilukuri K. Mohan

Electrical Engineering and Computer Science - Technical Reports

This paper investigates the semantics of conditional term rewriting systems with negation which do not satisfy useful properties like termination. It is shown that the approach used by Fitting [5] for Prolog-style logic programs is applicable in this context. A monotone operator is developed, whose fixpoints describe the semantics of conditional rewriting. Several examples illustrate this semantics for non-terminating rewrite systems which could not be easily handled by previous approaches.

Go to article

Balancing A Pipeline By Folding, Per Brinch Hansen Dec 1990

Balancing A Pipeline By Folding, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

A pipeline for Householder reduction is folded several times across an array of processors to achieve approximate load balancing. The performance of the folded pipeline is analyzed and measured on a Computing Surface.

Go to article

The All-Pairs Pipeline, Per Brinch Hansen Dec 1990

The All-Pairs Pipeline, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

An all-pairs problem is a computation on every possible subset consisting of two elements chosen from a set of n elements. N-body simulation and Householder reduction are all-pairs problems. The paper defines the all-pairs problem concisely by means of precedence matrices and derives a parallel algorithm. The algorithm is presented in both coarse-grain and medium-grain form. The all-pairs paradigm is illustrated by a pipeline for Householder reduction of a matrix to triangular form.

Go to article

Analyzing Images Containing Multiple Sparse Patterns With Neural Networks, Rangachari Anand, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka Dec 1990

Analyzing Images Containing Multiple Sparse Patterns With Neural Networks, Rangachari Anand, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

We have addressed the problem of analyzing images containing multiple sparse overlapped patterns. This problem arises naturally when analyzing the composition of organic macromolecules using data gathered from their NMR spectra. Using a neural network approach, we have obtained excellent results in using NMR data to analyze the presence of amino acids in protein molecules. We have achieved high correct classification percentages (about 87%) for images containing as many as five substantially distorted overlapping patterns.

Go to article

First Prev Next Last