Open Access. Powered by Scholars. Published by Universities.®
- Institution
- Keyword
-
- Adaptive computing systems (1)
- Algorithms (1)
- Appropriate cost (1)
- Approximation algorithms (1)
- Channel routing (1)
-
- Communication capability (1)
- Computer security -- Innnovations (1)
- Computer viruses -- Prevention (1)
- Constraint satisfaction problem (1)
- Empirical comparison (1)
- Fat-pyramid (1)
- Fat-tree (1)
- Gener-purpose parallel computing (1)
- HPF/Fortran 90D application development (1)
- Hypercube (1)
- Mesh (1)
- Network (1)
- Operating systems (Computers) -- Design and construction (1)
- Parallel computation (1)
- Performance evaluation (1)
- Performance experimentation & predition (1)
- Placement (1)
- Randomized rounding (1)
- Real-time data processing (1)
- Routing strategy (1)
- Scheduling -- Computer programs (1)
- Single-layer routing (1)
- System & application characterization (1)
- VLSI (1)
- Wire routing (1)
- Publication
Articles 1 - 30 of 42
Full-Text Articles in Engineering
A Specialization Toolkit To Increase The Diversity Of Operating Systems, Calton Pu, Andrew P. Black, Crispin Cowan, Jonathan Walpole, Charles Consel
A Specialization Toolkit To Increase The Diversity Of Operating Systems, Calton Pu, Andrew P. Black, Crispin Cowan, Jonathan Walpole, Charles Consel
Computer Science Faculty Publications and Presentations
Virus and worm attacks that exploit system implementation details can be countered with a diversified set of implementations. Furthermore, immune systems show that attacks from previously unknown organisms require effective dynamic response. In the Synthetix project, we have been developing a specialization toolkit to improve the performance of operating system kernels. The toolkit helps programmers generate and manage diverse specialized implementations of software modules. The Tempo-C specializer tool generates different versions for both compile-time and run-time specialization. We are now adapting the toolkit to improve operating system survivability against implementations attacks.
Multimedia Applications Require Adaptive Cpu Scheduling, Veronica Baiceanu, Crispin Cowan, Dylan Mcnamee, Calton Pu, Jonathan Walpole
Multimedia Applications Require Adaptive Cpu Scheduling, Veronica Baiceanu, Crispin Cowan, Dylan Mcnamee, Calton Pu, Jonathan Walpole
Computer Science Faculty Publications and Presentations
CPU scheduling and admission testing for multimedia applications have been extensively studied, and various solutions have been proposed using assorted simplifying assumptions. However, we believe that the complexity and dynamic behavior of multimedia applications and systems make static solutions hard to apply in real-world situations. We are analyzing the difficulties that arise when applying the rate-monotonic (RM) scheduling algorithm and the corresponding admission tests for CPU management, in the context of real multimedia applications running on real systems. RM requires statically predictable, periodic workloads, and while multimedia applications appear to be periodic, in practice they exhibit numerous variabilities in workload. …
An Empirical Comparison Of Networks And Routing Strategies For Parallel Computation, Ronald I. Greenberg, Lee Guan
An Empirical Comparison Of Networks And Routing Strategies For Parallel Computation, Ronald I. Greenberg, Lee Guan
Computer Science: Faculty Publications and Other Works
This paper compares message routing capabilities of important networks proposed for general-purpose parallel computing. All the networks have been proven to have some type of universality property, i.e., an ability to simulate other networks of comparable cost with modest slowdown, using appropriate cost and communication models. But in this paper we seek an empirical comparison of communication capability under typical direct use rather than an analysis of worst-case results for simulating message traffic of another network.
Mass Limit For The Standard Model Higgs Boson With The Full Lep I Aleph Data Sample, Buskulic, D.; Et Al., M. Thulasidas
Mass Limit For The Standard Model Higgs Boson With The Full Lep I Aleph Data Sample, Buskulic, D.; Et Al., M. Thulasidas
Research Collection School Of Computing and Information Systems
The reaction e+e− → HZ∗ is used to search for the standard model Higgs boson in the Hνν and the Hℓ+ℓ− channels. The data sample corresponds to about 4.5 million hadronic Z decays collected by the ALEPH experiment at LEP from 1989 to 1995 at centre-of-mass energies at and around the Z peak. Three candidate events are found in the Hμ+μ− channel, in agreement with the expected background from the electroweak process e+e− ℓ+ℓ−qq. This search results in a 95% C.L. lower limit on the Higgs boson mass of 63.9 GeV/c2.
Search For Cp Violation In The Decay Z → B B̄ G, Buskulic, D.; Et Al., M. Thulasidas
Search For Cp Violation In The Decay Z → B B̄ G, Buskulic, D.; Et Al., M. Thulasidas
Research Collection School Of Computing and Information Systems
About three million hadronic decays of the Z collected by ALEPH in the years 1991 to 1994 are used to search for anomalous CP violation beyond the Standard Model in the decay Z → bb̄g. The study is performed by analyzing angular correlations between the two quarks and the gluon in three-jet events and by measuring the differential two-jet rate. No signal of CP violation is found. For the combinations of anomalous CP violating couplings, ĥb = ĥAbgVh - ĥVbgAb and hb* = √ĥVb2 + ĥAb2, limits of | ĥb | b*
An Empirical Comparison Of Area-Universal And Other Parallel Computing Networks, Ronald I. Greenberg, Lee Guan
An Empirical Comparison Of Area-Universal And Other Parallel Computing Networks, Ronald I. Greenberg, Lee Guan
Computer Science: Faculty Publications and Other Works
This paper provides empirical comparison of the communication capabilities of two area-universal networks, the fat-tree and the fat-pyramid, to the popular mesh and hypercube networks for parallel computation. While area-universal networks have been proven capable of simulating, with modest slowdown, any computation of any other network of comparable area, prior work has generally left open the question of how area-universal networks compare to other networks in practice. Comparisons are performed using techniques of throughput and latency analysis that have previously been applied to k-ary n-cube networks and using various existing models to equate the hardware cost of the networks being …
Search For Charginos And Neutralinos With R-Parity Violation At √S = 130 And 136 Gev, Buskulic, D.; Et Al., M. Thulasidas
Search For Charginos And Neutralinos With R-Parity Violation At √S = 130 And 136 Gev, Buskulic, D.; Et Al., M. Thulasidas
Research Collection School Of Computing and Information Systems
Searches for charginos and neutralinos produced in e +e - collisions at centre-of-mass energies of 130 and 136 GeV have been performed under the assumptions that R-parity is not conserved, that the dominant R-parity violating coupling involves only leptonic fields, and that the lifetime of the lightest supersymmetric particle can be neglected. In the 5.7 pb -1 data sample collected by ALEPH, no candidate events were found. As a result, chargino and neutralino masses and couplings are constrained and the domains previously excluded at LEP1 are extended.
Single-Layer Channel Routing And Placement With Single-Sided Nets, Ronald I. Greenberg, Jau-Der Shih
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 …
Concept Hierarchy Memory Model: A Neural Architecture For Conceptual Knowledge Representation, Learning, And Commonsense Reasoning, Ah-Hwee Tan, Hui-Shin Vivien Soon
Concept Hierarchy Memory Model: A Neural Architecture For Conceptual Knowledge Representation, Learning, And Commonsense Reasoning, Ah-Hwee Tan, Hui-Shin Vivien Soon
Research Collection School Of Computing and Information Systems
This article introduces a neural network based cognitive architecture termed Concept Hierarchy Memory Model (CHMM) for conceptual knowledge representation and commonsense reasoning. CHMM is composed of two subnetworks: a Concept Formation Network (CFN), that acquires concepts based on their sensory representations; and a Concept Hierarchy Network (CHN), that encodes hierarchical relationships between concepts. Based on Adaptive Resonance Associative Map (ARAM), a supervised Adaptive Resonance Theory (ART) model, CHMM provides a systematic treatment for concept formation and organization of a concept hierarchy. Specifically, a concept can be learned by sampling activities across multiple sensory fields. By chunking relations between concepts as …
Efficient User Space Protocol Implementations With Qos Guarantees Using Real-Time Upcalls, R. Gopalakrishnan, Guru M. Parulkar
Efficient User Space Protocol Implementations With Qos Guarantees Using Real-Time Upcalls, R. Gopalakrishnan, Guru M. Parulkar
All Computer Science and Engineering Research
Real-time upcalls (RTUs) are an operating systems mechanism to provide quality-of-service (QoS) guarantees to network applications, and to efficiently implement protocols in user space with (QoS) guarantees. Traditionally, threads (and real-time extensions to threads) have been used to structure concurrent activities in user space protocol implementations. However, preemptive scheduling required for real-time threads leads to excessive context switching, and introduces the need for expensive concurrency control mechanisms such as locking. The RTU mechanism exploits the iterative nature of protocol processing to eliminate the need for locking, and reduce asynchronous preemption, while ensuring real-time operation. In addition to efficiency, eliminating the …
Compile-Time Performance Prediction Of Hpf/Fortran 90d, Manish Parashar, Salim Hariri
Compile-Time Performance Prediction Of Hpf/Fortran 90d, Manish Parashar, Salim Hariri
Electrical Engineering and Computer Science - All Scholarship
In this paper we present an interpretive approach for accurate and cost-effective performance prediction in a high performance computing environment, and describe the design of a compile-time HPF/Fortran 90D performance prediction framework based on this approach. The performance prediction framework has been implemented as a part of the HPF/Fortran 90D application development environment that integrates it with a HPF/Fortran 90D compiler and a functional interpreter. The current implementation of the environment framework is targeted to the iPSC/860 hypercube multicomputer system. A set of benchmarking kernels and application codes have been used to validate the accuracy, utility, and usability of the …
Design Of A Gigabit Atm Switch, Tom Chaney, Andrew Fingerhut, Margaret Flucke, Jonathan S. Turner
Design Of A Gigabit Atm Switch, Tom Chaney, Andrew Fingerhut, Margaret Flucke, Jonathan S. Turner
All Computer Science and Engineering Research
This report describes the design and implementation of a gigabit ATM switching system supporting link rates from 150 Mb/s to 2.4 Gb/s, with a uniquely efficient multicast switch architecture that enables the construction of systems with essentially constant per port costs for configurations ranging from 8 to 4096 ports and system capacities approaching 1- Tb.s. The system design supports many-to-one and many-to-many forms of multicast, in addition to the usual one-to-many. It also provides multicast virtual paths, constant time configuration of multicast connections and an efficient packet-level discard method, that can achieve 100% link efficiencies, without large buffers.
Reconsidering Fragmentation And Reassembly, Girish P. Chandranmenon, George Varghese
Reconsidering Fragmentation And Reassembly, Girish P. Chandranmenon, George Varghese
All Computer Science and Engineering Research
We reconsider several issues related to fragmentation and reassembly in IP. We first reconsider reassembly. We describe a simple expected case optimization that improves reassembly performance to 38 instructions per fragment if the fragments arrive in FIFO order (the same assumption made in header prediction) which has been implemented in the NetBSD kernel. Next, we introduce the new idea of Graceful Intermediate Reassembly (GIR), which is a generalization of the existing IP mechanisms of destination and hop-by-hop reassembly. In GIR, we coalesce the fragments at an intermediate router in order to use the largest sized packets on its outgoing interface. …
Optimal Solution Of Off-Line And On-Line Generalized Caching, Saied Hosseini-Khayat, Jerome R. Cox
Optimal Solution Of Off-Line And On-Line Generalized Caching, Saied Hosseini-Khayat, Jerome R. Cox
All Computer Science and Engineering Research
Network traffic can be reduced significantly if caching is utilized effectively. As an effort in this direction we study the replacement problem that arises in caching of multimedia objects. The size of objects and the cost of cache misses are assumed non-uniform. The non-uniformity of size is inherent in multimedia objects, and the non-uniformity of cost is due to the non-uniformity of size and the fact that the objects are scattered throughout the network. Although a special case of this problem, i.e. the case of uniform size and cost, has been extensively studied, the general case needs a great deal …
End-User Construction And Configuration Of Distributed Multimedia Applications, Terrance Paul Mccartney
End-User Construction And Configuration Of Distributed Multimedia Applications, Terrance Paul Mccartney
All Computer Science and Engineering Research
Distributed multimedia applications supported by a global electronic infrastructure have tremendous potential for providing users with customized communication and computation environments. Since communication and computation requirements vary by context and change dynamically, it is unlikely that off-the-shelf applications will anticipate the needs of all users. Therefore, empowering end-users to create their own customized applications for both communication and computation is an important challenge. This dissertation presents several mechanisms that enable end-users to create and configure distributed multimedia applications, including end-users construction direct manipulation graphical users interface (GUIs) and application management of distributed multimedia applications over the Internet.
Design Of Nonblocking Atm Networks, J. Andrew Fingerhut, Rob Jackson, Subhash Suri, Jonathan S. Turner
Design Of Nonblocking Atm Networks, J. Andrew Fingerhut, Rob Jackson, Subhash Suri, Jonathan S. Turner
All Computer Science and Engineering Research
This paper considers the problem of designing ATM networks that are nonblocking with respect to virtual circuit requests, subject to specified constraints on the traffic. In this paper, we focus on global traffic constraints that simply limit the total entering and exiting traffic at each switching system. After reviewing prior results for linear link costs, we introduce a more realistic link cost model, and develop a number of results using it. We also describe a technique for converting tree-structured networks to nonblocking hierarchical networks satisfying limits on the capacity of any single switch.
Designing Minimum Cost Nonblocking Communication Networks, J. Andrew Fingerhut, Subhash Suri, Jonathan S. Turner
Designing Minimum Cost Nonblocking Communication Networks, J. Andrew Fingerhut, Subhash Suri, Jonathan S. Turner
All Computer Science and Engineering Research
This paper addresses the problem of topological design of ATM (and similar) communication networks. We formulate the problem from a worst-case point of view, seeking network desings that, subject to specified traffic constraints, are nonblocking for point-to-point and multicast virtual circuits. Within this model we give various conditions under which star networks are optimal or near-optimal. These conditions are approximately satisfied in many common situations making the results of practical significance. An important consequence of these results is that, where they apply, there is no added cost for nonblocking multicast communication, relative to networks that are nonblocking for point-to-point traffic …
Leap Forward Virtual Clock: An O(Loglogn) Fair Queuing Scheme With Guaranteed Delays And Throughput Fairness, Subhash Suri, George Varghese, Girish P. Chandranmenon
Leap Forward Virtual Clock: An O(Loglogn) Fair Queuing Scheme With Guaranteed Delays And Throughput Fairness, Subhash Suri, George Varghese, Girish P. Chandranmenon
All Computer Science and Engineering Research
We describe an efficient fair queuing scheme, Leap Forward Virtual Clock, that provides end-to-end delay bounds almost identical to that of PGPS fair queuing, along with throughput fairness. Our scheme can be implemented with a worst-case time O(loglogN) per packet guaranteed delay and throughput fairness. As its name suggests, our scheme is based on Zhang's virtual clock. While the original virtual clock scheme does not achieve throughput fairness, we can modify it with a simple leap forward mechanism that keeps the server clock from lagging too far behind the packet tags. We prove that our scheme guarantees a fair share …
Vaudeville: A High Performance, Voice-Activated Teleconferencing Application, Jyoti K. Parwatikar, T. Paul Mccartney, John D. Dehart, Maynard Engebretson, Kenneth J. Goldman
Vaudeville: A High Performance, Voice-Activated Teleconferencing Application, Jyoti K. Parwatikar, T. Paul Mccartney, John D. Dehart, Maynard Engebretson, Kenneth J. Goldman
All Computer Science and Engineering Research
We present a voice-activated, hands-off, ATM-based video conferencing application. The application, called Vaudeville, features high quality NTSC video, voice-activated audio transmission, audio bridging of two audio streams, and voice-activated video switching. It supports multiple simultaneous multi-party conferences using a scalable multicast mechanism. We describe how Vaudeville was built using a component-based distributed programming environment. We also describe the algorithms used to contorl the audio and video of the applciation. Audio and video are encoded in hardware using an ATM hardware multimedia interface.
Design And Implementation Of A Practical Security-Conscious Electronic Polling System, Lorrie Faith Cranor, Ron K. Cytron
Design And Implementation Of A Practical Security-Conscious Electronic Polling System, Lorrie Faith Cranor, Ron K. Cytron
All Computer Science and Engineering Research
We present the design and implementation of Sensus, a practical, secure and private system for conducting surveys and elections over computer networks. Expanding on the work of Fujioka, Okamoto, and Ohta, Sensus uses blind signatures to ensure that only registered voters can vote and that each registered voter only votes once, while at the same time maintaining voters' privacy. Sensus allows voters to verify independently that their votes were counted correctly, and anonymously challenge the results should their votes be miscounted. We outline seven desirable properties of voting systems and show that Sensus satisfied these properties well, in some cases …
New Results On Generalized Caching, Saied Hosseini-Khayat
New Results On Generalized Caching, Saied Hosseini-Khayat
All Computer Science and Engineering Research
We report a number of new results in generalized caching. This problem arises in modern computer networks in which data objects of various sizes are transmitted frequently. First it is shown that its optimal solution is NP-complete. Then we explore two methods of obtaining nearly optimal answers based on the dynamic programming algorithm that we provided in [5]. These methods enable a trade-off between optimality and speed. It is also shown that LFD (the longest forward distance algorithm which is the optimal policy in the classical case), is no longer optimal but is competitive. We also prove that LRU remains …
Bringing Real-Time Scheduling Theory And Practice Closer For Multimedia Computing, R. Gopalakrishnan, Guru M. Parulkar
Bringing Real-Time Scheduling Theory And Practice Closer For Multimedia Computing, R. Gopalakrishnan, Guru M. Parulkar
All Computer Science and Engineering Research
This paper seeks to bridge the gap between theory and practice of real-time scheduling in the domain of multimedia computer systems. We show that scheduling algorithms that are good in theory, often have practical limitations. However when these algorithms are modified based on practical considerations, existing theoretical results cannot be used as they are. In this paper we motivate the need for new scheduling schemes for multimedia protocol processing, and demonstrate their real-time performance in our prototype implementation. We then explain the observed results by analysis and measurement. More specifically, we show that using strict preemption can introduce overheads in …
Distributed Stream Filtering For Database Applications, William M. Shapiro, Kenneth J. Goldman
Distributed Stream Filtering For Database Applications, William M. Shapiro, Kenneth J. Goldman
All Computer Science and Engineering Research
Distributed stream filtering is a mechanism for implementing a new class of real-time applications with distributed processing requirements. These applications require scalable architectures to support the efficient processing and multiplexing of large volumes of continuously generated data. This paper provides an overview of a stream-oriented model for database query processing and presents a supporting implementation. To facilitate distributed stream filtering, we introduce several new query processing operations, including pipelined filtering that efficiently joins and eliminates duplicates from database streams and a new join method, the progressive join, that joins streams of tuples. Finally, recognizing that the stream-oriented model results in …
An Algorithm For Message Delivery To Mobile Units, Amy L. Murphy, Gruia-Catalin Roman, George Varghese
An Algorithm For Message Delivery To Mobile Units, Amy L. Murphy, Gruia-Catalin Roman, George Varghese
All Computer Science and Engineering Research
With recent advances in wireless communication and the ubiquity of laptops, mobile computing has become an important research area. An essential problem in mobile computing is the delivery of a message from a source to either a single mobile node, unicast, or to a group of mobile nodes, multicast. Standard solutions used in Mobile IP and cellular phones for the unicast problem rely on tracking the mobile unit. Tracking solutions scale badly when mobile nodes move frequently, and do not generalize well to multicast delivery. Our paper proposes a new message delivery algorithm for micromobility based on a modification of …
Mobile Unity Coordination Constructs Applied To Packet Forwarding For Mobile Hosts, Peter J. Mccann, Gruia-Catalin Roman
Mobile Unity Coordination Constructs Applied To Packet Forwarding For Mobile Hosts, Peter J. Mccann, Gruia-Catalin Roman
All Computer Science and Engineering Research
With recent advances in wireless communication technology, mobile computing is an increasingly important area of research. A mobile system is one where independently executing components may migrate through some space during the course of the computation, and where the pattern of connectivity among the components changes as they move in and out of proximity. Mobile UNITY is a language and logic for specifying and reasoning about mobile systems, the components of which must operate in a highly decoupled way. In this paper it is argued that Mobile UNITY contributes to the modular development of system specifications because of the declarative …
A Usability Study Of End-User Construction Of Direct Manipulation User Interfaces, T Paul Mccartney
A Usability Study Of End-User Construction Of Direct Manipulation User Interfaces, T Paul Mccartney
All Computer Science and Engineering Research
This paper describes an empirical study of end-users that tested the usability of The Programmers' Playground graphical environment. The Programmers' Playground is a software library and run-time system for constructing distributed multimedia applications. Playground's graphical environment enables end-users to create direct manipulation graphical user interfaces (GUIs) and to dynamically configure communication among distributed application components. In this study, 28 end-users with no prior experience in distributed computing or user interface construction were timed and evaluated on several tasks using our graphical environment. Tasks included the use of direct and indirect constraint relationships, visual configuration of distributed applications, and graphical user …
Building Distributed Applications With Design Patterns, Gruia-Catalin Roman, James C. Hu
Building Distributed Applications With Design Patterns, Gruia-Catalin Roman, James C. Hu
All Computer Science and Engineering Research
Design patterns are a topic of great current interest within the object-oriented programming community. The motivation is both economical and intellectual. On one hand, there is the hope of establishing a common culture and language that fosters communicatino and growth in the software engineering field. While a community dominated by empiricism is seeking to achieve higher levels of formality by capturing its experiences in the form of catalogs of design patterns, another community, deeply rooted in formal thinking, is seeking to make its mark on the every day workings of the software engineering process. Distributed algorithms and the heuristics used …
Automatic Pcb Inspection Algorithms: A Survey, Madhav Moganti, Fikret Ercal, Cihan H. Dagli, Shou Tsunekawa
Automatic Pcb Inspection Algorithms: A Survey, Madhav Moganti, Fikret Ercal, Cihan H. Dagli, Shou Tsunekawa
Computer Science Faculty Research & Creative Works
The importance of the inspection process has been magnified by the requirements of the modern manufacturing environment. In electronics mass-production manufacturing facilities, an attempt is often made to achieve 100% quality assurance of all parts, subassemblies, and finished goods. A variety of approaches for automated visual inspection of printed circuits have been reported over the past two decades. In this survey, algorithms and techniques for the automated inspection of printed circuit boards are examined. A classification tree for these algorithms is presented and the algorithms are grouped according to this classification. This survey concentrates mainly on image analysis and fault …
Analysis Of Mpeg Compressed Video Traffic, Jerome R. Cox Jr., O. Matthew Beal
Analysis Of Mpeg Compressed Video Traffic, Jerome R. Cox Jr., O. Matthew Beal
All Computer Science and Engineering Research
This paper outlines a study of MPEG compressed video sequences and simulation of multiplexed video traffic in the ATM environment. A number of statistical characteristics including autocorrelation and variance of MPEG-1 compressed video sequences are used to characterize the 16 sample traces used in this study. From these measurements, a preliminary model is developed which utilizes basic measurements of the individual component video sequences to predict bandwidth requirements and cell loss of the multiplexed video traffic.
Simulation Of Asynchronous Instruction Pipelines, Chia-Hsing Chien, Mark A. Franklin
Simulation Of Asynchronous Instruction Pipelines, Chia-Hsing Chien, Mark A. Franklin
All Computer Science and Engineering Research
This paper presents the ARAS simulator with which asynchronous instruction pipelines can be modelled, simulated and displayed. ARAS allows one to construct instruction pipelines by preparing various configuration files. Using these files and a number of benchmark programs, performance of the instruction pipelines can be obtained. The performance of asynchronous instruction pipelines can also be compared to synchronous case. Thus, one can decide the optimal design for instruction pipelines in asynchornous or synchronous cases and explore the deisng space of asynchronous instruction pipeline architectures.