Browsing LCS Technical Memos (1974 - 2003) by Title
Now showing items 48-67 of 492
-
'C: A Language for High-Level, Efficient, and Machine-independant Dynamic Code Generation
Dynamic code generation allows specialized code sequences to be crafted using runtime information. Since this information is by definition not available statically, the use of dynamic code generation can achieve performance ... -
CAMAC: Group Manipulation System
(1975-03)CAMAC is a collection of group manipulation progams with an easy to use interface. With groups defined by either generating permutations or generators and relations the system can find coset tables, normalizers, centralizers, ... -
Can Statistical Zero Knowledge be made Non-interactive? or On the Relationship of SZK and NISZK
(1999-09)We extend the study of non-interactive statistical zero-knowledge proofs. Our main focus is to compare the class NISZK of problems possessing such non-interactive proofs to the class SZK of problems possessing interactive ... -
A Case Study of Shared Memory and Message Passing: The Triangle Puzzle
(1995-01)This thesis is the first controlled case study that compares shared-memory and message-passing implementations of an application that solves the triangle puzzle and runs on actual hardware: only the communication interfaces ... -
Cellular Automata '86 Conference
(1986-12) -
Cellular Automata Supercomputers for Fluid Dynamics Modeling
(1985-12)We report recent developments in the modeling of fluid dynamics, and give experimental results (including dynamical exponents) obtained using cellular automata machines. Because of their locality and uniformity, cellular ... -
Characterizing Second Order Logic with First Order Quantifiers
(1978-02)A language Q is defined and given semantics, the formulae of which are quantifier-free first-order matrices prefixed by combinations of finite partially ordered first-order quantifiers. It is shown that Q is equivalent in ... -
Charge-Based Proportional Scheduling
(1996-05)Most priority-based schedulers lack the ability to control the relative execution rates of applications. A recent scheme, called lottery scheduling [WW94], uses randomization to control the execution rates of threads in ... -
Cilk: An Efficient Multithreaded Runtime System
(1996-01)Cilk (pronounced "silk") is a C-based runtime system for multithreaded parallel programming. In this paper, we document the efficiency of the Cilk work-stealing scheduler, both empirically and analytically. We show that ... -
Circuit Analysis of Self-timed Elements for NMOS VLSI Systems
(1982-05)Scalingof VLSI digital systems introduces new problems to the design of synchronous systems, due to the disproportional increase in wire delays with the decrease in transistor sizes. One the other hand, the asynchronous ... -
Circuit-size Lower Bounds and Non-reducibility to Sparse Sets
(1981-10)As remarked in Cook (1980), we do not know any nonlinear lower bound on the circuit-size of a language in P or even in NP. The best known lower bound seems to be due to Paul (1975). In this paper we show that first for ... -
A Class of Boolean Functions with Linear Combinatorial Complexity
(1974-10)In this paper we investigate the combinatorial complexity of Boolean functions satisfying a certain property, P^nk,m. A function of n variable has the P^nk,m property if there are at least m functions obtainable from each ... -
A Class of Finite Computations Structures Supporting the Fast Fourier Transform
(1973-03)The Fast Fourier Transform (FFT) and modular arithmetic are two distinct techniques which recently have been employed to increase the efficiency of numerous algorithms in the area of symbolic and algebraic manipulation. -
A Client-Server Oriented Algorithm for Virtually Synchronous Group Membership in WANs
(1999-06)We describe a novel scalable group membership algorithm designed for wide area networks(WANs.) Our membership service does not evolve from existing LAN-oriented membership services; it was designed explicitly for WANs. -
Closing the Window of Vulnerability in Multiphase Memory Transcations
(1992-06)Multiprocessor architects have begun to explore several mechanisms such as prefetching, context-switching and software-assisted dynamic cache-coherence, which transform single-phase memory transactions in conventional ... -
The Colored Ticket Algorithm
(1983-08)Upper and lower bounds are proved for shared space requirements for solution of a problem involving resource allocation among asynchronous processes. The problem is to allocate some number, k≥1, of resources, in an environment ... -
Column-associative Caches: A Technique for Reducing the Miss Rate of Direct-mapped Caches
(1993-11)Direct-mapped caches are a popular design choice for high-performance processors; unfortunately, direct-mapped caches suffer systematic interference misses when more than one address map into the same cache set. This paper ... -
Combinatorial Algorithms for the Generalized Circulation Problem
(1988-05)We consider a generalization of the maximum flow problem in which the amounts of flow entering and leaving an arc are linearly related. More precisely, if x(e) units of flow enter an arc e, x(e) ?(e) units arrive at the ...