It is shown that the greatest common divisor of two n-bit integers (given in the usual binary representation) can be computed in time O(n) on a linear systolic array of O(n) cells. Comments Only the...
Fast Algorithms for Manipulating Formal Power Series (2008)
The classical algorithms require order n ~ operations to compute the first n terms in the reversion of a power series or the composition of two series, and order nelog n operations if the fast Founer...
Natasha Devroye, Patrick Mitran, Hideki Ochiai, Saeed S. Ghassemzadeh, H. T. Kung, Vahid Tarokh
2 Abstract Nodes and/or clusters of a wireless network operating on the same frequency can operate using three different paradigms: 1) Competition: Traditionally, this is information theoretically...
R. P. Brent, H. T. Kung, F. T. Luk
We survey some recent results on linear-time algorithms for systolic arrays. In particular, we show how the greatest common divisor (GCD) of two polynomials of degree n over a finite field can be...
In our earlier papers [1, 3], we gave fast algorithms for manipulating dense univariate power series. In this paper, fast algorithms for composition and reversion of dense multivariate power series...
Richard P. Brent, H. T. Kung, J. L. Hennessy, D. A. Patterson, Morgan Kaufmann
With VLSI architectures, the chip area and design regularity represent a better measure of cost than the conventional gate count. We show that addition of n-bit binary numbers can be performed on a...
Tsong Ho. Wu, Dennis T. Kong, Richard C. Lau, An Economic, Flavio Bonomi, Kerry W. Fendick, ...
pp.25-39, March/April 1995.
R. P. Brent, H. T. Kung, R. P. Brent, H. T. Kung
The classical algorithms require order n 3 operations to compute the first n terms in the reversion of a power series or the composition of two series, and order n 2 log n if the fast Fourier...
On-Demand Link Padding in Traffic Anonymizing (2008)
Chen-mou Cheng, H. T. Kung, Koan-sin Tan
We consider the problem of using artificially generated cover traffic to hide the network paths used by an application against an adversarial observer who can monitor network traffic and perform...
Two Approaches for Providing QoS on the Internet 1. “Freeway model ”-- integrated (2008)
H. T. Kung, Services Internet (intserv
• Build a dedicated highway or “circuit” between communicating points 2. “Doctor’s model ”-- differentiated services (diffserv) • Mark a doctor’s vehicle (e.g., ambulance) or...
Parallel Use of Multiple Channels in Multi-hop 802.11 Wireless Networks (2008)
Chen-mou Cheng, Pai-hsiang Hsiao, H. T. Kung, Dario Vlah
We consider parallel use of multiple channels in a multi-radio, multi-hop 802.11 wireless network, with the goal of maximizing the total multi-hop throughput. We first quantify several fundamental...
Chen-mou Cheng, Pai-hsiang Hsiao, H. T. Kung, Dario Vlah
In this paper, we propose transmit antenna selection based on receiver feedback of channel information obtained via linklayer probing. Furthermore, we report the performance gain of the proposed...
Chen-mou Cheng, Pai-hsiang Hsiao, H. T. Kung, Dario Vlah
We evaluate the performance impact of adjacent channel interference (ACI) in multi-hop wireless networks based on dual-radio 802.11a nodes. Although these nodes use chipsets that satisfy the...
Chen-mou Cheng, Yu-sheng Huang, H. T. Kung, Chun-hsin Wu
Abstract—We present an overlay network routing scheme, called Path Probing Relay Routing (PPRR), which is capable of promptly switching to alternative paths when the direct paths provided by the...
Maximizing Throughput of UAV-Relaying Networks with the Load-Carry-and-Deliver Paradigm (2008)
Chen-mou Cheng, Pai-hsiang Hsiao, H. T. Kung, Dario Vlah
We consider the task of using one or more Unmanned Aerial Vehicles (UAVs) to relay messages between two distant ground nodes. For delay-tolerant applications like latency-insensitive bulk data...
Achieving Fairness in Generalized Processor Sharing for Network Switches (2008)
Raymond Yim Natasha, Raymond Yim, Natasha Devroye, Vahid Tarokh, H. T. Kung
In Generalized Processor Sharing (GPS), the goal of the scheduler is to maximize the processor utilization, while maintaining a rate guarantee and fairness in the bandwidth allocation to each input...
MOSS: A Mobile Operating Systems Substrate (2007)
J. Bradley Chen, J. Bradley Chen, H. T. Kung, H. T. Kung, Margo Seltzer, Margo Seltzer
The Mobile Operating System Substrate (MOSS) is a new system architecture for wireless mobile computing being developed at Harvard. MOSS provides highly efficient, robust and flexible virtual device...
Infrastructure for Research towards Ubiquitous Information Systems (2007)
Barbara Grosz, H. T. Kung, Margo Seltzer, Stuart Shieber, Michael Smith
Experiences with Using a High Quality MPEG Video Server to Aid Classroom Teaching (2007)
Mark Gaynor, Vijak Sethaput, H.T. Kung
In the Spring of 1998 we provided all the lectures of Harvard's network course (CS143) on-line with a high quality MPEG real-time video-on-demand server. Our system allowed students to view...
Multi-List Scheduling on Nectar: Software and Experiment (2007)
) I-Chen Wu School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213 H. T. Kung Division of Applied Sciences, Harvard University, Cambridge, MA 02138 April 1993 1 Summary One of...
With VLSI architecture, the chip area and design regularity represent a better measure of cost than the conventional gate count. We show that addition of n-bit binary numbers can be performed on a...
Content Networks: Taxonomy and New Approaches (2007)
Kihong Park, Walter Willinger (editors, H. T. Kung, C. H. Wu
In this article we describe a taxonomy for content networks and suggest new architectures for such networks. In recent years, many types of content networks have been developed in various contexts,...
TCP Trunking for Bandwidth Management of Aggregate Traffic (2007)
TCP trunking is a novel way of applying TCP congestion control to bandwidth management of aggregate traffic. This is accomplished by setting up a separate TCP connection to probe network congestion,...
Oh-soon Shin, H. T. Kung, Vahid Tarokh, Senior Member
Abstract — In this paper, we construct a family of block orthogonal Golay sequences that have low peak-to-mean envelope power ratio (PMEPR) as well as blockwise orthogonal properties. We then...
This paper considers communications and network systems whose properties are characterized by the gaps of the leading eigenvalues of A H A for a matrix A. It is shown that a sufficient and necessary...
A Hub Matrix Theory and Applications to Wireless Communications (2007)
This paper considers communications and network systems whose properties are characterized by the gaps of the leading eigenvalues of AHA for a matrix A. It is shown that a sufficient and necessary...
A Hub Matrix Theory and Applications to Wireless Communications (2007)
This paper considers communications and network systems whose properties are characterized by the gaps of the leading eigenvalues of AHA for a matrix A. It is shown that a sufficient and necessary...
Multilist Scheduling. A New Parallel Programming Model. (2006)
Wu, I-Chen, Kung, H. T., Steenkiste, Peter, O'Hallaron, David, Thompson, Gerald
Parallel programming requires task scheduling to optimize performance; this primarily involves balancing the load over the processors. In many cases, it is critical to perform task scheduling at...
Chen-mou Cheng, Pai-hsiang Hsiao, H. T. Kung, Dario Vlah
We report measured performance of 802.11a wireless links from an unmanned aerial vehicle (UAV) to ground stations. In a set of field experiments, we record the received signal strength indicator...
Design of an OFDM cooperative space-time diversity system (2005)
Oh-soon Shin, Albert M. Chan, H. T. Kung, Vahid Tarokh, Senior Member
Abstract—In this paper, we propose a wireless system that realizes theoretical benefits of space-time cooperation. Specifically, we design a space-time cooperative system based on orthogonal...
TCP with sender-based delay control (2003)
This paper describes a congestion control method for TCP that adjusts the transmission rate of a TCP connection by changing not only the congestion window size as in normal TCP, but also by delaying...
Streaming Video over TCP with Receiver-based Delay Control (2003)
Pai-Hsiang Hsiao, H.T. Kung, Koan-Sin Tan
This paper describes a method of extending TCP so that TCP connections can effectively carry hierarchically-encoded layered video streams, while being friendly to other competing connections. We call...
Parallel Algorithms for Solving Triangular Linear Systems with Small Parallelism, (2002)
The problem of solving triangular linear systems of size n on a parallel computer with small parallelism is considered. Assume that the time is measured by the number of parallel steps of any...
O((n log n)sup 3/2) Algorithms for Composition and Reversion of Power Series. (2002)
Prepared in cooperation with Australian National Univ., Canberra. Computer Centre.
Bounds on the Speed-Up of Parallel Evaluation of Recurrences, (2002)
To understand the performance of parallel computers such as ILLIAC IV and C.mmp, the largest speed-up that can be obtained for a given task must be known. If there are k processors, the largest...
Fast Algorithms for Partial Fraction Decomposition. (2002)
The partial fraction decomposition of a proper rational function whose denominator has degree n and is given in general factored form can be done in O(n (log n) squared) operations in the worst case....
Sorting on a Mesh-Connected Parallel Computer. (2002)
Two algorithms are presented for sorting M to the 2nd power elements on an nxn mesh-connected processor array that require O(n) routing and comparison steps. The best previous algorithm takes time...
Fast Algorithms for Manipulating Formal Power Series. (2002)
The classical algorithms require O(n sup 3) operations to compute the first n terms in the reversion of a power series or the composition of two series, and O((n sup 2) log n) operations if the fast...
All Algebraic Functions Can Be Computed Fast. (2002)
The expansions of algebraic functions can be computed 'fast' using the Newton Polygon Process and any 'normal' iteration. Let M(j) be the number of operations sufficient to multiply two jth degree...
Parallel Execution of a Sequence of Tasks on an Asynchronous Multiprocessor. (2002)
Baudet,G. M., Brent,R. P., Kung,H. T.
Given a sequence of tasks to be performed serially, a parallel algorithm is proposed to accelerate the execution of the tasks on an asynchronous multiprocessor by taking advantage of fluctuations in...
On the Average Number of Maxima in a Set of Vectors and Applications. (2002)
Bentley,J. L., Kung,H. T., Schkolnick,M., Thompson,C. D.
A maximal vector of a set is one which is not less than any other vector in all components. A recurrence relation is derived for computing the average number of maximal vectors in a set of n vectors...
An Efficient Parallel Garbage Collection System and Its Correctness Proof. (2002)
An efficient system to perform garbage collection in parallel with list operations is proposed and its correctness is proven. The system consists of two independent processes sharing a common memory....
Systolic Arrays for (VLSI). (2002)
Kung,H. T., Leiserson,Charles E.
A systolic system is a network of processors which rhythmically compute and pass data through the system. Physiologists use the work 'systole' to refer to the rhythmically recurrent contraction of...
A Regular Layout for Parallel Adders. (2002)
With VLSI architecture the chip area is a better measure of cost than the conventional gate count. We show that addition of n-bit binary numbers can be performed on a chip in time proportional to log...
Concurrent Manipulation of Binary Search Trees. Revision. (2002)
The concurrent manipulation of a binary search tree is considered in this paper. The systems presented can support any number of concurrent processes which perform searching, insertion, deletion, and...
Design of Special-Purpose VLSI Chips: Example and Opinions. (2002)
This paper identifies important steps in the design of a special purpose VLSI chip, and argues that the most crucial step is the design of the underlying algorithm. Because the algorithm determines...
On Optimistic Methods for Concurrency Control. (2002)
Most current approaches to concurrency control in database systems rely on locking of a data objects as a control mechanism. In this paper, two families of non-locking concurrency controls are...
Two Papers on a Tree-Structured Parallel Computer. (2002)
This report consists of two papers describing various aspects of a new tree-structured parallel computer. The first paper, 'A tree machine for searching problems' by J. L. Bentley and H. T. Kung,...
The Area-Time Complexity of Binary Multiplication, (2002)
We consider the problem of performing multiplication of n-bit binary numbers on a chip. Let A denote the chip area, and T the time required to perform multiplication. Using a model of computation...
Systolic (VLSI) Arrays for Relational Database Operations. Revision. (2002)
This paper proposes the use of VLSI technology to perform relational database operations directly in hardware. It is shown that relational computations, such as intersection, remove-duplicates,...
I/O Complexity: The Red-Blue Pebble Game. (2002)
In this paper, the red-blue pebble game is proposed to model the input-output complexity of algorithms. Using the pebble game formulation, a number of lower bound results for the I/O (Input/Output)...
A Systolic 2-D Convolution Chip. (2002)
This paper describes a chip for performing the 2-D (two-dimensional) convolution in signal and image processing. The chip, based on a systolic design, consists of essentially only one type of simple...
Recognize Regular Languages with Programmable Building-Blocks. (2002)
This paper introduces a new programmable building-block for recognition of regular languages. By combining three types of basic cells a circuit for recognizing any regular language can be constructed...
MISE: Machine for In-System Evaluation of Custom VLSI Chips. (2002)
Bisiani,R., Foster,M. J., Kung,H. T., Oflazer,K.
This paper identifies some of the key research problems that one encounters in specifying, designing, testing and demonstrating a custom chip in relation to the application system in which it will be...
Synchronizing Large Systolic Arrays. (2002)
Parallel computing structures consist of many processors operating simultaneously. If a concurrent structure is regular, as in the case of systolic array, it may be convenient to think of all...
A Two-Level Pipelined Systolic Array for Multi-Dimensional Convolution, (2002)
Kung,H. T., Ruane,Lawrence M., Yen,David W. L.
This paper describes a systolic array for the computation of n-dimensional (n-D) convolutions of any positive integer n. Systolic systems usually achieve high performance by allowing computations to...
An Algebra for VLSI Algorithm Design. (2002)
Algorithms designed for VLSI implementation are usually parallel and two-dimensional in the sense that many processing elements laid out on a silicon surface can operate simultaneously. These...
A Systolic Algorithm for Integer GCD Computation. Revision, (2002)
In this document the authors show that the greatest common divisor of two n-bit integers (given in the usual binary representation) can be computed in time O(n) on a linear array of O(n) identical...
Use of spectral analysis in defense against DoS attacks (2002)
Chen-mou Cheng, H. T. Kung, Koan-sin Tan
Abstract-- We propose using spectral analysis to identify normal TCP traffic so that it will not be dropped or rate-limited in defense against denial of service (DoS) attacks. The approach can reduce...
MotusNet: A content network (2001)
H. T. Kung, Pai-hsiang Hsiao, Adon Hwang, Conrad Nobili, Michael Vernal, Dario Vlah, ...
Abstract – MotusNet is a content network in which the addressable objects, contents, are decoupled from the physical nodes that carry them. The content names in MotusNet are hierarchical, so that...
Use of TCP Decoupling in Improving TCP Performance over Wireless Networks (2001)
We propose using the TCP decoupling approach...
Load-Balancing Routing for Wireless Access Networks (2001)
Pai-hsiang Hsiao, Adon Hwang, H. T. Kung, Dario Vlah
Abstract-- Widespread use of wireless devices presents new challenges for network operators, who need to provide service to ever larger numbers of mobile end users, while ensuring Quality-of-Service...
The Real Options Approach to Standards for Building Network-based Services (2001)
Mark Gaynor, Scott Bradner, Marco Iansiti, H. T. Kung
In this paper, we show the economic value of flexibility in standards by linking the business concept of market uncertainty to the technical aspects of designing standards and implementing...
GPSR: Greedy Perimeter Stateless Routing for Wireless Networks (2000)
We present Greedy Perimeter Stateless Routing (GPSR), a novel routing protocol for wireless datagram networks that uses the positions of routers and a packet's destination to make packet...
Greedy Perimeter Stateless Routing for Wireless Networks (2000)
We present Greedy Perimeter Stateless Routing (GPSR), a novel routing protocol for wireless datagram networks that uses the positions of routers and a packet’s destination to make packet forwarding...
Greedy Perimeter Stateless Routing for Wireless Networks (2000)
We present Greedy Perimeter Stateless Routing (GPSR), a novel routing protocol for wireless datagram networks that uses the positions of routers and a packet’s destination to make packet forwarding...
The Complexity of Parallel Evaluation of Linear Recurrences. (1999)
The concept of computers such as C.mmp and ILLIAC 4 is to achieve computational speed-up by performing several operations simultaneously with parallel processors. This type of computer organization...
A TCP trunk is an IP tunnel under TCP control, capable of carrying packets from any number of user flows. By exploiting properties of TCP, a TCP trunk provides elastic and reliable transmission over...
Optimal Order of One-Point and Multipoint Iteration, (1998)
The problem is to calculate a simple zero of a non-linear function f by iteration. The authors exhibit a family of iterations of order 2 sup (n-1) which use n evaluations of f and no derivative...
Computational Complexity of One-Point and Multipoint Iteration, (1998)
Let phi be an iteration for approximating the solution of a problem f. A new efficiency measure e(phi,f) is defined. For a given problem f, the authors define the optimal efficiency E(f) and...
Optimal Order and Efficiency for Iterations with Two Evaluations. (1998)
The problem is to calculate a simple zero of a non-linear function f. The authors consider rational iterations without memory which use two evaluations of f or its derivatives. It is shown that the...
The Warp Computer: Architecture, Implementation, and Performance. (1998)
Annaratone,Marco, Arnould,Emmanuel, Gross,Thomas, Kung,H. T., Lam,Monica
The Warps machine is a systolic array computer of linearly connected cells, each of which is a programmable processor capable of performing 10 million floating-point operations per second (10...
Program Translation Tools for Systolic Arrays. (1998)
Our work over the last year has concentrated on two different areas: The automatic generation of programs for a systolic array (the Warp machine) from a program representation that is independent on...
Research on Signal Processing Supercomputers. (1998)
Signal processing is an area where the required computational bandwidth in an application can be unbounded. Applications such as radar, sonar and communications already call for signal processing...
Neural Network Simulation at Warp Speed: How We Got 17 Million Connections per Second. (1998)
Pomerleau, Dean A., Gusciora, George L., Touretzky, David S., Kung, H. T.
We describe a fast back-propagation algorithm for a linear array of processors. Results of an implementation of this algorithm on Warp1, a ten processor, programmable systolic array computer, are...
Fault-Tolerance and Two-Level Pipelining in VLSI Systolic Arrays, (1998)
This paper addresses two important issues in systolic array designs: fault-tolerance and two-level pipelining. The proposed 'systolic' fault-tolerant scheme maintains the original data flow pattern...
Systolic (VLSI) Arrays for Relational Database Operations. Revision. (1998)
Kung, H. T., Lehman, Phillip L.
This paper proposes the use of VLSI technology to perform relational database operations directly in hardware. It is shown that relational computations, such as intersection, remove-duplicates,...
Communications Neural Net Processors. (1998)
This report covers several neural net algorithms. The report describes the rationale for their developments and the details of their operation. The report also addresses the efficient implementation...
Automatic Tools for Developing Fine-Grained Signal Processing Programs on Multicomputers. (1998)
O'Hallaron, David R., Kung, H. T.
During the course of this contract we developed the first system that integrates task and data parallelism in a uniform compiler framework. The compiler which is called Fx, translates a dialect of...
GPSR: Greedy Perimeter Stateless Routing for Wireless Networks (1998)
We present Greedy Perimeter Stateless Routing (GPSR), a novel routing protocol for wireless datagram networks that used the positions of routers and a packet's destination to make packet forwarding...
Enhancing Transport Networks with Internet Protocols (1998)
Alan Chapman Nortel, H. T. Kung
Transport networks are facing new challenges and opportunities because of the explosive growth of data traffic. Besides having to meet the ever increasing bandwidth demand, transport networks need to...
A PC-Based ATM Link Delay Simulator (1998)
Mark Gaynor, Brad Karp, H. T. Kung
We have implemented a low-cost, flexible, and easy-touse Link Delay Simulator (LDS) for OC-3 (155 Mbps) ATM links using a commodity Pentium PC equipped with a single PCI ATM host adapter. The LDS is...
BPB: Bounded Peak Bandwidth GMB: Guaranteed Minimum Bandwidth (1998)
Want “Elastic ” services between two communicating edge nodes A and B: • Allow bandwidth overflow when extra network bandwidths become available • Can guarantee minimum bandwidth and bound...
called “Cell Switched Router (CSR)”. (1998)
H. T. Kung, Q (virtual Lans, Tag Switching
Both efforts had origins in ATM: • ATM switches-->IP switching. • ATM Forum tried to define VLANs in 1994, and decided to let IEEE do it. Both efforts intend to realize certain advantages that...
Dynamic Neighbor Discovery and Loop-Free, Multi-Hop Routing for Wireless, Mobile Networks (1998)
We present the Harvard User-Level Metricom Radio driver (HUMR), a substrate for development of wireless datagram routing protocols, and Any-Path Routing without Loops (APRL), a distance-vector,...
Dynamic Neighbor Discovery and LoopFree, Multi-Hop Routing for Wireless, Mobile Networks (1998)
We present the Harvard User-Level Metricom Radio driver (HUMR), a substrate for development of wireless datagram routing protocols, and Any-Path Routing without Loops (APRL), a distance-vector,...
Automatic Quality Of Service In Ip Networks (1997)
Alan Chapman, Nortel Technology, H.T. Kung
Multi-media IP networks will require that a data flow be given a certain Quality of Service (QoS) within the network. The proposed reservation protocol (RSVP) for IP (and signalling in ATM networks)...
Park, Myoung Jin., Robinson, John T., Kung, H. T.
Thesis (M.S.)--California State University, San Bernardino, 1996.
Credit-Based Flow Control for ATM Networks (1995)
Blackwell Chang Kung, T. Blackwell, K. Chang, H. T. Kung, D. Lin
In credit-based flow control for ATM networks, switch buffer space is first allocated to each virtual circuit (VC) and then credit control is applied to the VC to prevent possible buffer overflow....
An Experimental Flow-Controlled Multicast ATM Switch (1994)
T. Blackwell, K. Chan, K. Chang, T. Charuhas, B. Karp, H. T. Kung, ...
BNR and Harvard have jointly designed an experimental ATM switch called CreditSwitch with sixteen 622-Mbps ports. Expected to be operational in early 1995, the switch will support credit-based flow...
An Experimental Flow-Controlled Multicast ATM Switch (1994)
T. Blackwell, K. Chan, K. Chang, T. Charuhas, B. Karp, H. T. Kung, ...
BNR and Harvard have jointly designed an experimental ATM switch called CreditSwitch with sixteen 622-Mbps ports. Expected to be operational in early 1995, the switch will support credit-based flow...
Credit-Based Flow Control for ATM Networks (1994)
Congestion control ensures that network resources are divided fairly and efficiently among competing connections. Although congestion control has been studied by researchers for a long time, very...
Credit-Based Flow Control for ATM Networks (1994)
Congestion control ensures that network resources are divided fairly and efficiently among competing connections. Although congestion control has been studied by researchers for a long time, very...
An Experimental Flow-Controlled Multicast ATM Switch (1994)
T. Blackwell, K. Chan, K. Chang, T. Charuhas, B. Karp, H. T. Kung, ...
BNR and Harvard have jointly designed an experimental ATM switch called CreditSwitch with sixteen 622-Mbps ports. Expected to be operational in early 1995, the switch will support credit-based flow...
Use of Link-by-Link Flow Control in Maximizing ATM Network Performance: Simulation Results (1993)
Simulations have been performed to verify the effectiveness of using link-by-link flow controlled virtual channels for maximizing ATM network performance. A simulator which accurately reflects the...
A Host Interface Architecture for High-Speed Networks (1992)
Peter Steenkiste, Brian D. Zill, H. T. Kung, Steven J. Schlick, Jim Hughes, Bob Kowalski, ...
This paper describes a new host interface architecture for high-speed networks operating at 800 of Mbit/second or higher rates. The architecture is targeted to achieve several 100s of Mbit/second...
Network-Based Multicomputers: An Emerging Parallel Architecture (1991)
H. T. Kung, Robert Sansom, Steven Schlick, Peter Steenkiste, Matthieu Arnould, Francois J. Bitz, ...
Multicomputers built around a general network are now a viable alternative to multicomputersbased ona system-specific interconnect because of architectural improvements in two areas. First, the...
Parallelizing a New Class of Large Applications over High-Speed Networks (1991)
H. T. Kung, Peter Steenkiste, Marco Gubitoso, Manpreet Khaira
Abstract parallel architecture. In both cases, the efforts require Several large applications have been parallelized that the persons responsible for the porting are on Nectar, a network-based...
A New Approach for Automatic Parallelization of Blocked Linear Algebra Computations (1991)
This paper describes a new approach for automatic generation of efficient parallel programs from sequential blocked linear algebra programs. By exploiting recent progress in finegrain parallel...
Communication Complexity for Parallel Divide-and-Conquer (1991)
This paper studies the relationship between parallel computation cost and communication cost for performing divide-and-conquer (D&C) computations on a parallel system of p processors. The...
Parallelizing a New Class of Large Applications over High-Speed Networks (1991)
H. T. Kung, Peter Steenkiste, Marco Gubitoso, Manpreet Khaira
Abstract parallel architecture. In both cases, the efforts require Several large applications have been parallelized that the persons responsible for the porting are on Nectar, a network-based...
Supporting Systolic and Memory Communication in iWarp (1990)
Shekhar Borkar, Robert Cohn, George Cox, Thomas Gross, H. T. Kung, Monica Lam, ...
TM general computing; whereas systolic communication is iWarp is a parallel architecture developed jointly by efficient and well suited for speed critical applications. Carnegie Mellon University and...
The design of Nectar: A network backplane for heterogeneous multicomputers (1989)
Emmanuel A. Arnould, H. T. Kung, Francois J. Bitz, Robert D. Sansom, Eric C. Cooper, Peter A. Steenkiste
Nectar is a "network backplane " for use in heterogeneous multicomputers. The initial system consists of a starshaped fiber-optic network with an aggregate bandwidth of 1.6...
iWarp: An Integrated Solution to High-Speed Parallel Computing (1988)
Shekhar Borkar, Robert Cohn, George Cox, Sha Gleason, Thomas Gross, H. T. Kung, ...
an iWarp cell; up to 64 MBytes of memory are directly addressable. A large array of iWarp cells will deliver an iWarp is a system architecture for high speed signal, image enormous computing...
The Warp Computer: Architecture, Implementation and Performance (1987)
Marco Annaratone, Emmanuel Arnould, Thomas Gross, H. T. Kung, Monica Lam, Onat Menzilcioglu, ...
Research under Contracts N00014-87-K-0385 and N00014-87-K-0533. Warp is a service mark of Camegie Mellon University. UNIX is a trademark of ATBLT Bell Laboratories. Sun-3 is a trademark of Sun...
Mapping Image Processing Operations onto a Linear Systolic Machine (1986)
H. T. Kung, Jon A. Webb, He Guggetiheitil, Fc~io\v It Ntld
1974 ufter rewiring his P1i.D. ciiycv thcw. Appointed to ProfP.sor in 1982. he is curreti(1j holding Shell Distingui.vlied
A. Bojanczyk, R. P. Brent, H. T. Kung
We propose a multiprocessor structure for solving a dense system of n linear equations. The solution is obtained in two stages. First, the matrix of coefficients is reduced to upper triangular form...
Some Linear-Time Algorithms for Systolic Arrays (1983)
Brent, Richard P., Kung, H. T., Luk, Franklin T.
We survey some recent results on linear-time and almost linear-time algorithms for one and two-dimensional systolic arrays. In particular, we show how the greatest common divisor (GCD) of two...
Some Linear-Time Algorithms for Systolic Arrays (1983)
Brent, Richard P., Kung, H. T., Luk, Franklin T.
We survey some recent results on linear-time and almost linear-time algorithms for one and two-dimensional systolic arrays. In particular, we show how the greatest common divisor (GCD) of two...
The problem of finding a greatest common divisor (GCD) of any two nonzero polynomials is fundamental to algebraic and symbolic computations, as well as to the decoder implementation for a variety of...
On optimistic methods for concurrency control (1981)
Most current approaches to concurrency control in database systems rely on locking of data objects as a control mechanism. In this paper, two families of nonlocking concurrency controls are...
The Area-Time Complexity of Binary Multiplication (1981)
ABSTRACT The problem of performing multtphcaUon of n-bit binary numbers on a chip is considered Let A denote the ch~p area and T the time reqmred to perform mult~phcation. By using a model of...
On optimistic methods for concurrency control (1981)
Most current approaches to concurrency control in database systems rely on locking of data objects as a control mechanism. In this paper, two families of nonlocking concurrency controls are...
On optimistic methods for concurrency control (1981)
Most current approaches to concurrency control in database systems rely on locking of data objects as a control mechanism. In this paper, two families of nonlocking concurrency controls are...
The chip complexity of binary arithmetic (1980)
The chip complexity of a computation is concerned with the chip area, A, and the time, T, required to perform the computation when implemented on a chip. An area-time product AT α, for α ≥ 0, is...
On the area of binary tree layouts (1980)
The binary tree is an important interconnection pattern for VLSI chip layouts. Suppose that the nodes are separated by at least unit distance and that a wire has unit width. The usual layout of a...
The problem of performing multiplication of n-bit numbers on a chip is considered. Let A denote the chip area and T the time required to perform multiplication. By using a model of computation which...
On the average number of maxima in a set of vectors and applications (1978)
J. L. Bentley, H. T. Kung, M. Schkolnick, C. D. Thompson
ABSTRACT. A maximal vector of a set ~s one which is not less than any other vector m all components We derive a recurrence relation for computing the average number of maxunal vectors m a set of n...
On finding the maxima of a set of vectors (1975)
H. T. Kung, F. Luccio, F. P. Preparata
ASSTRACT. Let U1, U2,..., Ud be totally ordered sets and let V be a set of n d-dimensional vectors In U ~ X Us.. X Ud. A partial ordering is defined on V in a natural way The problem of finding all...
Thesis (M.S.)--Victoria University of Wellington, New Zealand, 1973.
Credit-Based Flow Control For ATM Networks: (0000)
Simulation, analysis, and experiments on switching hardware have shown that for a wide variety of traffic patterns, credit control is fair, uses links efficiently, minimizes delay, and guarantees no...
Credit-Based Flow Control For ATM Networks:
Simulation, analysis, and experiments on switching hardware have shown that for a wide variety of traffic patterns, credit control is fair, uses links efficiently, minimizes delay, and guarantees no...
Chen, W.L., Luan, Y.C., Shieh, M.C., Chen, S.T., Kung, H.T., Soong, K.L, ...
The conventional approach for radiation protection is based on the ICRP's linear, no threshold (LNT) model of radiation carcinogenesis, which implies that ionizing radiation is always harmful, no...