In this paper, we present a comprehensive security architecture, Flexible Secure Execution Environment (FlexSEE), for confidential computing in modern cloud environments. FlexSEE does not require the trust of system software on the compute server and guarantees that the user data is visible only in non-privileged mode to a designated program trusted by the data owner on a designated hardware, thus protecting the data from an untrusted hardware, hypervisor, OS, or other users' applications, on the compute server.

Nearly matching upper and lower bounds are derived for the I/O complexity of the Toom-Cook-k (or Toom-k) algorithm computing the products of two integers, each represented with n digits in a given base s, in a two-level storage hierarchy with M words of fast memory, with different digits stored in different memory words. An IOAk (n, M) = Ω ([n/M)logk(2k–1) M) lower bound on the I/O complexity is established, by a technique that combines an analysis of the size of the dominators of suitable sub-CDAGs of the Toom-Cook-k CDAG (Computational Directed Acyclic Graph) and the analysis of a function, which we call “Partial Grigoriev's flow”, which captures the amount of information to be transferred between specific subsets of input and output variables, by any algorithm that solves the integer multiplication problem. The lower bound applies even if the recomputation of partial results is allowed. A careful implementation of the Toom-Cook-fc algorithm, assuming that M = Ω (k3 logs k), is also developed and analyzed, leading to an I/O complexity upper bound that is within a factor O(k2) of the corresponding lower bound, hence asymptotically optimal for fixed k. Both the lower and the upper bounds are actually derived in the more general case where the value of k is allowed to vary with the level of recursion, although the quantitative expressions become more involved. Extensions of the lower bound for a parallel model with P processors are also discussed.

We present a novel approach to context-free grammar parsing that is based on generating a sequence of grammars called derivative grammars from a given context-free grammar and input string. The generation of the derivative grammars is described by a few simple inference rules. We present an O ( n 2 ) space and O ( n 3 ) time recognition algorithm, which can be extended to generate parse trees in O ( n 3 ) time and O ( n 2 log n ) space. Derivative grammars can be viewed as a symbolic approach to implementing the notion of derivative languages , which was introduced by Brzozowski. Might and others have explored an operational approach to implementing derivative languages in which the context-free grammar is encoded as a collection of recursive algebraic data types in a functional language like Haskell. Functional language implementation features like knot-tying and lazy evaluation are exploited to ensure that parsing is done correctly and efficiently in spite of complications like left-recursion. In contrast, our symbolic approach using inference rules can be implemented easily in any programming language and we obtain better space bounds for parsing. Reifying derivative languages by encoding them symbolically as grammars also enables formal connections to be made for the first time between the derivatives approach and classical parsing methods like the Earley and LL/LR parsers. In particular, we show that the sets of Earley items maintained by the Earley parser implicitly encode derivative grammars and we give a procedure for producing derivative grammars from these sets. Conversely, we show that our derivative grammar recognizer can be transformed into the Earley recognizer by optimizing some of its bookkeeping. These results suggest that derivative grammars may provide a new foundation for context-free grammar recognition and parsing.

A framework is proposed for the design and analysis of network-oblivious algorithms, namely algorithms that can run unchanged, yet efficiently, on a variety of machines characterized by different degrees of parallelism and communication capabilities. The framework prescribes that a network-oblivious algorithm be specified on a parallel model of computation where the only parameter is the problem’s input size, and then evaluated on a model with two parameters, capturing parallelism granularity and communication latency. It is shown that for a wide class of network-oblivious algorithms, optimality in the latter model implies optimality in the decomposable bulk synchronous parallel model, which is known to effectively describe a wide and significant class of parallel platforms. The proposed framework can be regarded as an attempt to port the notion of obliviousness, well established in the context of cache hierarchies, to the realm of parallel computation. Its effectiveness is illustrated by providing optimal network-oblivious algorithms for a number of key problems. Some limitations of the oblivious approach are also discussed.

The capability of the Random Access Machine (RAM) to execute any instruction in constant time is not realizable, due to fundamental physical constraints on the minimum size of devices and on the maximum speed of signals. This work explores how well the ideal RAM performance can be approximated, for significant classes of computations, by machines whose building blocks have constant size and are connected at a constant distance. A novel memory structure is proposed, which is pipelined (can accept a new request at each cycle) and hierarchical , exhibiting optimal latency a ( x ) = O ( x 1/ d ) to address x , in d -dimensional realizations. In spite of block-transfer or other memory-pipeline capabilities, a number of previous machine models do not achieve a full overlap of memory accesses. These are examples of machines with explicit data movement . It is shown that there are direct-flow computations (without branches and indirect accesses) that require time superlinear in the number of instructions, on all such machines. To circumvent the explicit-data-movement constraints, the Speculative Prefetcher (SP) and the Speculative Prefetcher and Evaluator (SPE) processors are developed. Both processors can execute any direct-flow program in linear time. The SPE also executes in linear time a class of loop programs that includes many significant algorithms. Even quicksort, a somewhat irregular, recursive algorithm admits a linear-time SPE implementation. A relation between instructions called address dependence is introduced, which limits memory-access overlap and can lead to superlinear time, as illustrated with the classical merging algorithm.

The design of algorithms that can run unchanged yet efficiently on a variety of machines characterized by different degrees of parallelism and communication capabilities is a highly desirable goal. We propose a framework for network-obliviousness based on a model of computation where the only parameter is the problem's input size. Algorithms are then evaluated on a model with two parameters, capturing parallelism and granularity of communication. We show that, for a wide class of network-oblivious algorithms, optimality in the latter model implies optimality in a block-variant of the decomposable BSP model, which effectively describes a wide and significant class of parallel platforms. We illustrate our framework by providing optimal network-oblivious algorithms for a few key problems, and also establish some negative results.

The Static Single Assignment (SSA) form is a program representation used in many optimizing compilers. The key step in converting a program to SSA form is called ϕ-placement. Many algorithms for ϕ-placement have been proposed in the literature, but the relationships between these algorithms are not well understood.In this article, we propose a framework within which we systematically derive (i) properties of the SSA form and (ii) ϕ-placement algorithms. This framework is based on a new relation called merge which captures succinctly the structure of a program's control flow graph that is relevant to its SSA form. The ϕ-placement algorithms we derive include most of the ones described in the literature, as well as several new ones. We also evaluate experimentally the performance of some of these algorithms on the SPEC92 benchmarks.Some of the algorithms described here are optimal for a single variable. However, their repeated application is not necessarily optimal for multiple variables. We conclude the article by describing such an optimal algorithm, based on the transitive reduction of the merge relation, for multi-variable ϕ-placement in structured programs. The problem for general programs remains open.

In a recent paper (SPAA'01), we have established that the Pipelined Hierarchical Random Access Machine (PH-RAM) is a powerful model of computation, where most of the memory latency can be hidden by concurrency of accesses. In the present work, we explore the physical feasibility of PH-RAMs.A pipelined hierarchical memory of size $S$ is characterized by two metrics: the access function α(χ), denoting the time required by an access to location $x$, and the pipeline period $p(S)$, denoting the minimum time between subsequent accesses that can be sustained. Physical constraints on minimum device size and maximum signal speed imply that, for a memory laid out in $d$ dimensions, a(χ)= Ω(χ1/d)$. We propose a novel memory organization scheme that can be specialized to yield optimal performance α(χ)=O(χ^1/d)$ and $p(S)=O(1)$, for any $d \geq 1$.Managing a large number of concurrent load and store instructions would pose a significant burden on a traditional RISC processor, requiring both a large register file and complex logic to properly synchronize instructions. We show how these obstacles can be circumvented by introducing the Scalable transPORT (SPORT) computer where a simple processor drives a version of our pipelined hierarchical memory capable of servicing memory-to-memory instructions. We show that SPORT provides a feasible, scalable implementation of the PH-RAM model.

We define a model of computation, called the Pipelined Hierarchical Random Access Machine with access function a (x), denoted the a(x)-PH-RAM. In this model, a processor interacts with a memory which can accept requests at a constant rate and satisfy each of the requests to the location x within a(x) units of time.We investigate memory management strategies that lead to time efficient implementations of arbitrary computations on a PH-RAM. We begin by developing the so called pipeline d decomposition-treememory management strategy, which can be tuned to the memory access function. Specifically, for a linear or sublinear access function a(x), w e define the concept of latency-hiding depth da(x) and show ho w an y computation of N operations can be implemented on an a(x)-PH-RAM in time T(N) = O(Nda(N)). In particular, T(N) = O(N log N) if a(x) = O(x), T(N) = O(N log log N) if a(x) = O(xΒ) with 0 Β T(N) = O(N log* N) if a(x) = O(log x).We develop lower bound techniques that allow to establish existential lower bounds on PH-RAMs. In particular, we exhibit computations for which T(N) = O(Nlog N/ log log N) when a(x) = O(x), T(N) = O(Nlog logN) when a(x) = O(xΒ) with 0 Β T(N) = O(N log* N) when a(x) = O(log x).The stated lower bounds show that the pipelined decomposition-tree strategy is existentially optimal for the latter case but indicates the potential for a modest, O(log log N) improvement for linear access functions. To realize this potential, a superpipelined decomposition-tree memory manager is proposed, which achieves T(N) = O(N log N/log log N).The pipelined decomposition-tree strategy can also be tuned to the computation, in order to exploit its temporal locality as characterized by the width parameters [9]. When the latter are suitably bounded, then T(N) = O(N) on any PH-RAM with linear or sublinear access function. Finally, we discuss how performance could benefit from parallelism in the data-dependence dag of the computation or from architectural enhancements, such as block-transfer primitives, and formulate various questions that deserve further investigation.

The control dependence relation plays a fundamental role in program restructuring and optimization. The usual representation of this relation is the control dependence graph (CDG), but the size of the CDG can grow quadratically with the input programs, even for structured programs. In this article, we introduce the augmented postdominator tree (APT) , a data structure which can be constructed in space and time proportional to the size of the program and which supports enumeration of a number of useful control dependence sets in time proportional to their size. Therefore, APT provides an optimal representation of control dependence. Specifically, the APT data structure supports enumeration of the set cd(e), which is the set of statements control dependent on control-flow edge e, of the set conds (w), which is the set of edges on which statement w is dependent, and of the set cdequiv ( w ), which is the set of statements having the same control dependences as w . Technically, APT can be viewed as a factored representation of the CDG where queries are processed using an approach known as filtering search.

We generalize the notion of dominance by defining a generalized dominance relation with respect to a set of paths in the control flow graph G = (V, E). This new definition leads to a generalized notion of control dependence, which includes standard control dependence and weak control dependence as special cases.If the set of paths underlying a generalized dominance relation satisfies some natural closure conditions, that dominance relation is tree-structured. Given this tree, the corresponding control dependence relation can be computed optimally by reduction to the Roman Chariots Problem, which we have developed previously for computing standard control dependence. More precisely, given linear preprocessing time and space, we can answer the (generalized version of the) so called cd, conds, and cdequiv queries in time proportional to the output of the query.To illustrate the utility of the framework, we show how weak control dependence can be computed optimally in O(|E|) preprocessing space and time. This improves the O(|V|3) time required by the best previous algorithm for this problem.

A quantitative comparison of the BSP and LogP models for parallel computation is developed.Very efficient cross simulations between the two models are derived, showing their substantial equivalence for algorithmic design guided by asymptotic analysis.It is also shown that the two models can be implemented with similar performance on most point-to-point networks.In conclusion, within the limits of our analysis that is mainly of asymptotic nature, BSP and LogP can be viewed as closely related variants within the bandwidth-latency framework for modeling parallel computation.BSP seems somewhat preferable due to greater simplicity and portability, and slightly greater power.

We study the most general communication paradigm on a multiprocessor, wherein each processor has a distinct message (of possibly distinct lengths) for each other processor. We study this paradigm, which we call chatting, on multiprocessors that do not allow messages once dispatched ever to be delayed on their routes. By insisting on oblivious routes for messages, we convert the communication problem to a pure scheduling problem. We introduce the notion of a virtual chatting schedule, and we show how efficient chatting schedules can often be produced from efficient virtual chatting schedules. We present a number of strategies for producing efficient virtual chatting schedules on a variety of network topologies.

Describes our experience with a newly-established international partnership between the Software Engineering Research Center (SERC), a university-based National Science Foundation (NSF) sponsored industrial research organization in the United States and an Italian industry-university team based in Padua, Italy.>

The control dependence relation is used extensively in restructuring compilers. This relation is usually represented using the control dependence graph; unfortunately, the size of this data structure can be quadratic in the size of the program, even for some structured programs. In this paper, we introduce a data structure called the augmented post-dominator tree (APT) which is constructed in space and time proportional to the size of the program, and which can answer control dependence queries in time proportional to the size of the output. Therefore, APT is an optimal representation of control dependence. We also show that using APT, we can compute SSA graphs, as well as sparse dataflow evaluator graphs, in time proportional to the size of the program. Finally, we put APT in perspective by showing that it can be viewed as a factored representation of control dependence graph in which filtered search is used to answer queries.

Upper bounds are derived for the processor-time tradeoffs of machines such as linear arrays and two-dimensional meshes, which are compatible with the physical limitation expressed by bounded-speed propagation of messages (due to the finiteness of the speed of light).It is shown that parallelism and locality combined may yield speedups superlinear in the number of processors.The speedups are inherent, due to the optimality of the obtained tradeoffs as established in a companion paper.Simulations are developed of multiprocessor machines by analogous machines with fewer processors.A crucial role is played by the hierarchical nature of the memory system.A divide-and-conquer technique for hierarchical memories is developed, based on the graph-theoretic notion of topological separator.For multiprocessors, this technique also requires a careful balance of memory access and interprocessor communication costs, which leads to non-intuitive orchestrations of the simulation process.

Two deterministic routing networks are presented: the pruned butterfly and the sorting fat-tree . Both networks are area-universal, that is, they can simulate any other routing network fitting in similar area with polylogarithmic slowdown. Previous area-universal networks were either for the off-line problem, where the message set to be routed is known in advance and substantial precomputation is permitted, or involved randomization, yielding results that hold only with high probability. The two networks introduced here are the first that are simultaneously deterministic and on-line, and they use two substantially different routing techniques. The performance of their routing algorithms depends on the difficulty of the problem instance, which is measured by a quantity λ known as the load factor. The pruned butterfly runs in time O (λlog 2 N ), is the number of possible sources and destinations for messages and λ is assumed to be polynomial in N . The sorting fat-tree algorithm runs in O (λ log N + log 2 N ) time for a restricted class of message sets including partial permutations. Other results of this work include a “flexible” circuit that is area-time optimal across a range of different input sizes and an area-time lower bound for routers based on wire-length arguments.

Language learnability is investigated in the Gold paradigm of inductive inference from positive data. Angluin gave a characterization of learnable families in this framework. Here, learnability of families of recursive languages is studied when the learner obeys certain natural constraints. Exactly learnable families are characterized for prudent learners with the following types of constraints: (0) conservative, (1) conservative and consistent, (2) conservative and responsive, and (3) conservative, consistent and responsive.

The problem of simulating a PRAM with n processors and memory size $m \geqslant n$ on an n-node bounded degree network is considered. A deterministic algorithm is presented that simulates an arbitrary PRAM step in $O(({{\log n\log m)} / {\log \log n)}}$ time in the worst case on an expander-based network. By extending a previously established lower bound, it is shown that the proposed simulation is optimal whenever $\Omega (n^{1 + \epsilon } ) \leqslant m \leqslant O(2^{(\log n)^\alpha } )$ for some positive real constants $ \epsilon $ and $\alpha $.

Language learning from positive data in the Gold model of inductive inference is investigated in a setting where the data can be modeled as a stochastic process. Specifically, the input strings are assumed to form a sequence of identically distributed, independent random variables, where the distribution depends on the language being presented. A scheme is developed which can be tuned to learn, with probability one, any family of recursive languages, given a recursive enumeration of total indices for the languages in the family and a procedure to compute a lower bound to the probability of occurrence of a given string in a given language. Variations of the scheme work under other assumptions, e.g., if the probabilities of the strings form a monotone sequence with respect to a given enumeration. The learning algorithm is rather simple and appears psychologically plausible. A more sophisticated version of the learner is also developed, based on a probabilistic version of the notion of tell-tale subset. This version yields, as a special case, Angluin's learner for the families of languages that are learnable from all texts (and not just from a set of texts of probability one).

Two deterministic routing networks, the pruned butterfly and the sorting fat-tree, are presented. Both networks are area universal, i.e. they can simulate with polylogarithmic slowdown, any other routing network fitting in similar area. Previous area-universal networks were either for the offline problem, where the message set to be routed is known in advance and substantial precomputation is permitted, or involved randomization, yielding results that hold only with high probability. The present networks are the first that are simultaneously deterministic and online, and they use two substantially different routing techniques. The performance of the routing algorithms depends on the difficulty of the problem instance, which is measured by a quantity lambda , known as the load factor. The pruned butterfly algorithm runs in time O( lambda log/sup 2/N), where N is the number of possible sources and destinations for messages and lambda is assumed to be polynomial in N. The sorting fat-free algorithm runs in O( lambda log N + log/sup 2/N) time for a restricted class of message sets, including partial permutations. Other results include a new type of sorting circuit, an area universal circuit, and an area-time lower bound for routers.>

The prefix problem consits of computing all the products $x_{0}x_{1}\cdots x_{j}(j = 0,\cdots, N-1)$, given a sequence ${\bf x} = (x_{0}, x_{1},\cdots , x_{N-1})$ of elements in a semigroup. It is shown that there are unbounded fan-in and fan-out Boolean circuits for the prefix problem with constant depth and linear size if and only if the Cayley graph of the semigroup does not contain a special type of cycle called monoidal cycle.

Article Optimal VLSI architectures for multidimensional DFT Share on Authors: G. Bilardi Department of Computer Science, Upson Hall, Cornell University, Ithaca, NY Department of Computer Science, Upson Hall, Cornell University, Ithaca, NYView Profile , S. W. Hornick Andersen Consulting, Center for Strategic Tech. Res., 100 S. Wacker, Chicago, IL Andersen Consulting, Center for Strategic Tech. Res., 100 S. Wacker, Chicago, ILView Profile , M. Sarrafzadeh Dept. of Elec. Eng. and Comp. Sci., The Technological Institute, Northwestern University, Evanston, IL Dept. of Elec. Eng. and Comp. Sci., The Technological Institute, Northwestern University, Evanston, ILView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 265–272https://doi.org/10.1145/72935.72963Online:01 March 1989Publication History 7citation284DownloadsMetricsTotal Citations7Total Downloads284Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The prefix problem consists of computing all the products x 0 x 1 … x j ( j = 0, … , N - 1), given a sequence x = ( x 0 , x 1 , … , x N- 1 ) of elements in a semigroup. In this paper we completely characterize the size-time complexity of computing prefixes with Boolean networks, which are synchronized interconnections of Boolean gates and one-bit storage devices. This complexity crucially depends upon two properties of the underlying semigroup, which we call cycle-freedom (no cycle of length greater than one in the Cayley graph of the semigroup), and memory-induciveness (arbitrarily long products of semigroup elements are true functions of all their factors). A nontrivial characterization is given of non-memory-inducive semigroups as those whose recurrent subsemigroup (formed by the elements with self-loops in the Cayley graph) is the direct product of a left-zero semigroup and a right-zero semigroup. Denoting by S and T size and computation time, respectively, we have S = Θ(( N / T )log( N / T )) for memory-inducive non-cycle-free semigroups, and S = Θ( N / T ) for all other semigroups. We have T ε [Ω(log N ), Ο( N )] for all semigroups, with the exception of those whose recurrent subsemigroup is a right-zero semigroup, for which T ε [Ω(1), Ο( N )]. The preceding results are also extended to the VLSI model of computation. Area-time optimal circuits are obtained for both boundary and nonboundary I/O protocols.

A parallel algorithm, called adaptive bitonic sorting, that runs on a PRAC (parallel random access computer), a shared-memory multiprocessor where fetch and store conflicts are disallowed, is proposed. On a P processors PRAC, the algorithm presented here achieves optimal performance $TP = O(N\log N)$, for any computation time T in the range $\Omega (\log ^2 N) \leqq T \leqq O(N\log N)$. Adaptive bitonic sorting also has a small constant factor, since it performs less than $2N\log N$ comparisons, and only a handful of operations per comparison.

A class of comparator networks obtained from the omega permutation network by replacing each switch with a comparator exchanger of arbitrary direction is considered. These networks are all isomorphic to each other, have merging capabilities, and can be used as building blocks of sorting networks in ways different from the standard merge-sort scheme. It is shown that the bitonic and balanced mergers are members of the class. These two networks were not previously known to be isomorphic.>

The prefix problem consists of computing all the products x0x1…xj (j=0, …, N - 1), given a sequence x = (x0, x1, …, xN - 1) of elements in a semigroup. In this paper we completely characterize the size-time complexity of computing prefixes with boolean networks, which are synchronized interconnections of Boolean gates and one-bit storage devices. This complexity crucially depends upon a property of the underlying semigroup, which we call cycle-freedom (no cycle of length greater than one in the Cayley graph of the semigroup). Denoting by S and T size and computation time, respectively, we have S = Θ((N/T) log(N/T)), for non-cycle-free semigroups, and S = Θ(N/T), for cycle-free semigroups. In both cases, T ∈ [Ω(logN), O(N)].

A generalization of a known class of parallel sorting algorithms is presented, together with a new interconnection to execute them. A VLSI implementation is also proposed, and its area-time performance is discussed. It is shown that an algorithm in the class is executable in O(log n) time by a chip occupying O(n2) area. The design is a typical instance of a ``hybrid architecture,'' resulting from the combination of well-known VLSI networks as the orthogonal trees and the cube-connected cycles; it also provably meets the AT2= Ω(n2log2n) lower bound for sorters of n words of length (1 + ε) log n (ε > 0).

A discrete-time system described by a truncated Volterra series whose input is a Markov chain is considered. A general explicit formula is derived for the mean value of the output process in terms of the transition-probability matrix of the input and of the Volterra kernels.

A generalization of a known class of parallel sorting algorithms is presented, together with a new interconnection to execute them. A VLSI implementation is also proposed, and its area-time performance is discussed. It is shown that an algorithm in the class is executable in O(logn) time by a chip occupying O(n2) area. The design is a typical instance of a “hybrid architecture”, resulting from the combination of well-known VLSI networks as the orthogonal trees and the cube-connected-cycles; it also provably meets the AT2=omegan2log2n) lower bound for sorters of n words of length (1+\epsilon)logn(\epsilon > O).

We propose a class of designs of a new interconnection network, the pleated cube-connected cycles (PCCC), which can impleement stable bitonic sorting of n records of size q in area A = O(q2n2/T2), where T, the computation time, is in the range [Ω(q log2n), O(q √n/(q+ log n))]. Thus, this network is an AT2,/R-optimal bitonic sorter in the synchronous VLSI model of computation under the word-local restriction.

This paper deals with the spectral analysis of digital processes obtained through memoryless functions of stationary Markov chains. Under the assumption that the Markov chain is ergodic, not necessarily acyclic, closed form formulas are derived for both the discrete part (spectral lines) and the continuous part of the spectral density. The results are applied at the output of a finite state sequential machine driven by a stationary Markov chain, which represents a general model of several situations of engineering interest. Finally, the theory is used to evaluate the spectrum of encoded and modulated digital signals.