|
Projects
Erez Petrank |
| Home |
| Publications |
| Courses |
| Projects |
| Committees |
| Collaborations |
| Patents |
| Students |
| Links |
| Bio |
| Hebrew |
| Content: |
|
Real-Time Concurrent Garbage Collection for Java, Memory Management with Sliding-views, Modern Reference-Counting Techniques, Advanced Mostly Concurrent Collection, Parallel Compaction and Copying, Local Heaps, Cache-Conscious Memory Placement, A Production JVM with the DLG collector |
|
Concurrent Zero-Knowledge,
Quantifying Knowledge Complexity, Studies in Multiparty Computation, Non-Interactive Zero-Knowledge, Identity Escrow, On the Hardness of Approximations, Data Structures Construction and Analysis. |
Real-Time Concurrent Memory Management for JavaHistorically, real-time systems were written in low-level code, limiting the real-time application to small simple programs. Recently, various implementations of real-time systems supporting high-level languages were presented. We take this technology a step further by providing concurrent real-time garbage collectors. Such collectors allow very high responsiveness, as the garbage collection is executed on separate cores, allowing the program to respond very quickly to events, with no interruption. The main challenge is in de-fragmenting the heap, moving objects while the application is accessing them concurrently. The first two papers present and study three possible alternatives: Stopless, Clover, and Chicken, all implemented in the Microsoft Bartok compiler for C#, showing pauses at the micro-seconds level, i.e., two orders of magnitude shorter than state-of-the-art real-time collectors. All three collectors are lock-free, guaranteeing application progress (and in particular, not using any locks). The third paper present a compiler method to reduce the overhead of the barriers, thus reducing the garbage collection overhead and improving application throughput. This method is also interesting for regular (not real-time) collectors. The fourth paper deals with stack scanning, which typically creates the most noticeable pause with on-the-fly collectors. The paper presents a method to break the stack scanning work into small pieces that can be executed incrementally and concurrently, shortening further the pause times that the application must take. Stack scanning is lock-free, making it a perfect fit for the real-time collectors presented herein.
Memory Management with Sliding-ViewsMany concurrent garbage collectors attempt to capture the view of the heap at one specific point in time, in spite of the heap being modified concurrently while the collector executes. This virtual snapshot view of the heap makes the collector easier to design and prove. We propose a different method, in which the collector work with a sliding view of the heap rather than a snapshot. The sliding view is a view of the heap in which the heap is read within a short interval, but not at a single point in time. Since the heap changes during this interval, the view is not a snapshot and may be thought of as "inconsistent". Nevertheless, we show that such a view can be used to reclaim unreachable objects safely. Sliding views collectors do not need to stop all the threads at a specific point in time to read their local variables. Thus, they allow extremely short pause times. We demonstrate this method in two papers, one implementing it with a reference-counting collector and the other with a mark-sweep collector. Reference-counting has traditionally been considered unsuitable for multi-processor systems. According to conventional wisdom, the update of reference slots and reference-counts required atomic or synchronized operations. In the first paper, we demonstrated that this is not the case by presenting a novel reference-counting algorithm suitable for a multi-processor system that does not require any synchronized operation in its write barrier (not even a compare-and-swap type of synchronization). A second novelty of this algorithm is that it allows the elimination of a large fraction of the reference-count updates, thus, drastically reducing the traditional reference-counting overhead. The paper included a full proof of the algorithm showing that it is safe (does not reclaim live objects) and live (eventually reclaims all unreachable objects). These techniques yield a non-obtrusive and efficient collector with pause times of around 1ms for standard benchmarks running on an SMP. A second paper exploited the above developed techniques to obtain a novel mark and sweep on-the-fly garbage collector with similar short pause times. In addition to being an effective mark and sweep on-the-fly collector standing on its own, this collector can also be used as a backup collector (collecting cyclic data structures) for the sliding-views reference-counting collector. These two algorithms fit perfectly sharing the same allocator, a similar data structure, and a similar JVM interface.
Modern Reference-Counting TechniquesThe study and use of reference counting on a multiprocessor has not been as extensive and thorough as the study of concurrent and parallel tracing collectors. The reason was that reference counting had three problems: inadequacy for use with multiprocessors, high overhead on reference-count updates, and inability to reclaim unreachable cyclic structures. The first two issues were dealt with by the sliding-views reference-counting collector, which constitute the first paper in this project. We first proposed the update coalescing method, which eliminated most of the count updates, and then we presented a write-barrier that eliminated the need for synchronization over the pointer updates for multiprocessors. Finally, we presented an on-the-fly version of the algorithm built on sliding-views. Going beyond the above important improvements to the basic reference-counting algorithm, we turned to further improving reference-counting collectors. The first goal was to use generations with reference counting. We started by proposing the use of reference counting in a generational collector such that the old generation is collected via reference counting and the young generation is collected via tracing. This configuration yields a nice improvement over non-generational reference counting. In a second work we proposed a non-conventional use of generations, denoted age-oriented collection, in which, unlike generational collectors, the entire heap is always collected, but, like generational collectors, each generation is treated differently during the collection. This achieves a further substantial improvement over the standard generational collector. Our second goal was to improve cycle collection for reference counting. In a third work we proposed a new algorithm for concurrent cycle collection. We improved over the efficiency of previous collectors, provided a simpler cycle collector adequate for running with the sliding-views reference-counting collector. Measurements show that cycle collection is advantageous when used with generations, most effectively with the age-oriented collector. This paper together with the age-oriented paper present our current understanding of the best way to run reference counting. It should be applied on old objects only and the generational hypothesis should be used according to the age-oriented collector. Finally, we investigated the use of prefetching to further improve the efficiency of the reference-counting collector. We proposed potential prefetching opportunities for a collector the follows the update coalescing methodology and report an implementation of a collector that employs such prefetching. The proposed prefetch instructions were inserted into the Jikes reference counting collector obtaining an average reduction of 8.7% of the memory management overheads.
Advanced Mostly Concurrent CollectionIn this project we designed and implemented a collector facing SMP demands. This collector was incorporated into the IBM production JVM. This collector builds on the mostly concurrent garbage collector proposed by Boehm et al. with several novel algorithmic ideas, improving the efficiency and shortening the pause times of the mostly concurrent collector substantially. We also made it parallel and incremental; we employed concurrent low-priority background GC threads to take advantage of processor idle time. Compared to the mature, well-optimized, parallel, stop-the-world mark-sweep IBM production collector, our collector prototype reduces the maximum pause time from 161ms to 46ms while only losing 11.5% throughput when running the SPECjbb2000 benchmark on a 600 MB heap on an 8-way PowerPC with 1.1 GHz processors.
Parallel Compaction and Copying for an SMPTypically, mark-sweep and reference-counting collectors are susceptible to fragmentation. Because the garbage collector does not move objects during the collection, the heap becomes more and more fragmented. Fragmentation increases the complexity of allocation and may prevent allocation of large objects. To ameliorate this problem, compaction algorithms are used to group the live objects together. The first paper proposes the Compressor, which is the most efficient compaction algorithm known today. It requires only a single heap pass plus a single pass on a small (mark-bits) table. The Compressor has a version that can run on several parallel compaction threads and a concurrent version that can run concurrently with the program threads. This work extends the one described in the second (earlier) paper, which proposes a parallel heap compaction algorithm appropriate for multiprocessors. That algorithm demonstrates high scalability when running in parallel but is also extremely efficient when running single-threaded on a uniprocessor. A copying collector compacts the heap during the collection. In the second paper we studied a parallel copying collector, and in the last one we made some observations on a concurrent copying collector.
Cache-Conscious Memory PlacementThe growing gap between the speed of memory access and cache access has made cache misses an influential factor in program efficiency. Much effort has been spent recently on reducing the number of cache misses during program runs. This effort has included wise rearranging of program code, cache-conscious data placement, and algorithmic modifications that improve the program cache behavior. In this work we investigated the complexity of finding the optimal placement of objects (or code) in the memory, in the sense that this placement reduces the cache misses to the minimum. We showed that this problem is one of the toughest amongst the interesting algorithmic problems in computer science. In particular, suppose one is given a sequence of memory accesses and has to place the data in the memory so as to minimize the number of cache misses for this sequence. We show that if P≠NP, then one cannot efficiently approximate the optimal solution even up to a very liberal approximation ratio.
Local HeapsIn this project we presented a memory management scheme for Java based on thread-local heaps. Assuming most objects are created and used by a single thread, it is desirable to free the memory manager from redundant synchronization for thread-local objects. Therefore, in our scheme each thread receives a partition of the heap in which it allocates its objects and in which it does local garbage collection without synchronization with other threads. We dynamically monitor to determine which objects are local and which are global. Furthermore, we suggested using profiling to identify allocation sites that almost exclusively allocate global objects, and allocate objects at these sites directly in a global area. This scheme substantially reduces the overall garbage collection times and eliminates most long pauses.
A Production JVM with the DLG CollectorsIn these project we designed and implemented an on-the-fly garbage collector based on the algorithm of Doligez, Leroy and Gonthier, denoted DLG. An on-the-fly collector is a collector that runs concurrently with the program threads and does not need to stop the program threads simultaneously. Such collectors achieve very low pause times on a multiprocessor. In the first paper we reported extending and adapting DLG for Java (e.g., adding support for weak references) and for modern multiprocessors without sequential consistency, and adding performance improvements (e.g., keeping track of the objects remaining to be traced). The performance advantage for our collector over a traditional stop-the-world collector increases as the number of threads increase; moreover, it provides uniformly low response times. In the second paper we reported an incorporation of generations into the said collector. The incorporation is non-trivial since an on-the-fly collector avoids explicit synchronization with the program threads. To the best of our knowledge, this is the first such incorporation reported in the literature. Comparing our on-the-fly collector with and without generations, it turns out that the generational collector performs better for most applications.
Concurrent Zero-KnowledgeZero knowledge proofs are a fascinating concept in the foundation of Cryptography. They allow conveying the proof of a statement without yielding any information to the verifier except for the validity of the proof. This seeming contradiction of convincing without yielding too much information made zero-knowledge an important construct in modern cryptographic protocols. A fundamental question about zero-knowledge protocols is whether their security is preserved when many instances of the protocol are executed in an asynchronous manner, denoted "concurrent zero-knowledge". We have investigated this question in a series of papers, for the standard "black-box" formulation. A first lower bound of five rounds on the communication complexity of a zero-knowledge interaction has been shown, separating concurrent zero-knowledge from other protocol compositions. Later, a strong lower bound was shown, i.e., that a concurrent zero-knowledge interaction essentially requires a logarithmic number of rounds. This turned out to be an (almost) optimal lower bound, as a matching upper bound was later discovered by a series of complementing work. In an attempt to build concurrent zero-knowledge protocols for NP, we have drastically improved a previously known protocol, reducing it's communication complexity from linear to poly-logarithmic, by building a more accurate simulator for the original protocol and presenting a novel simulation schedule. This simulator has later been refined by Prabhakaran et al. to reduce the complexity to an almost logarithmic one, thus, essentially matching the previously obtained lower bounds.
Quantifying Knowledge ComplexityA fundamental measure for the security of a protocol is the amount of information that leaks during an interaction. The goal of this project was to rigorously quantify and then study the amount of knowledge that a party obtains during an interaction. Gaining "Knowledge" in this context was interpreted in the most basic sense of "being able to compute more". We started by proposing definitions for the knowledge complexity of an interaction. Using the fundamental simulation concept, several rigorous definitions were proposed and their relations are thoroughly studied. Next, it was formally proven that a rich hierarchy of protocols exists with increasing knowledge complexity. Next, we studied the complexity of languages that have an interactive proof with low knowledge complexity. A series of papers with gradually improving mathematical techniques have finally led to showing that if a language has an interactive proof with logarithmic knowledge complexity, then it is both in the AM and in the coAM complexity classes.
Studies in Multiparty ComputationA general formulation of most cryptographic tasks is the formulation of multiparty computation. In this setting, a set of parties wish to jointly compute a function of their inputs, while preserving security in the case that some subset of them are corrupted. In this project we study several topics in secure multiparty computation. The first study was about the properties that can be obtained for general multiparty computation. The typical security properties considered in the literature are privacy, correctness, independence of inputs, guaranteed output delivery and fairness. Until now, all works in this area either considered an honest majority and then provided full security including output delivery and fairness, (but security can be completely compromised when the majority is not honest). A different set of protocols can work in the presence of a corrupted majority, but they do not guarantee output delivery, even with only one corrupted party. In this first work, we studied the possibility of obtaining general protocols for multiparty computation that simultaneously guaranteed security (but allowing abort) in the case that an arbitrary number of parties are corrupted and full security (including guaranteed output delivery) in the case that only a minority of the parties are corrupted. In a second work we studied the manner in which computational assumptions are used for the secure computation of non-trivial functionalities in the setting of no honest majority. For this case, we asked whether secure protocols can use the underlying primitives (e.g., one-way trapdoor permutation) in a black-box way, or they must refer to the code that computes this primitive. All known constructions used the underlying primitive in a nonblack-box way (requiring to prove in zero-knowledge statements that relate to the primitive). In this paper, we present protocols that use only black-box access to a family of trapdoor permutations or to a homomorphic public-key encryption scheme. The result is a protocol whose communication complexity is independent of the computational complexity of the underlying primitive and whose computational complexity grows only linearly with that of the underlying primitive. This is the first protocol to exhibit these properties. Finally, in a third work, we studied oblivious
transfers. Oblivious transfer is a powerful cryptographic primitive that may
be used to implement a wide variety of
Non-Interactive Zero-KnowledgeAn important setting of zero-knowledge is that of non-interactive zero-knowledge in the shared random string model, introduced by Blum Feldman and Micali. Non-interactive zero-knowledge (NIZK) protocols are useful for several higher level constructions, most notably public-key crypto systems secure against chosen-ciphertext attacks. In this work, we presented an efficient NIZK proof for any language in NP, based on general complexity assumptions. Our protocol is still the most efficient general NIZK protocol known today. In particular, the asymptotic complexity of this protocol matches the complexity of protocols that were built on specific algebraic assumptions, and the number of committed bits matches, up to a constant, the number of committed bits by the most efficient known interactive zero-knowledge proof systems for NP.
Identity EscrowWe introduce the concept of escrowed
identity, an application of key-escrow ideas to the problem of
authentication. In escrowed identity, one party A does not
give his identity to another party B, but rather gives him
information that would allow an authorized third party E to determine
A's identity. However, B receives a guarantee that E
can indeed determine A's identity. We consider a number of possible
features of escrowed identity schemes, and describe a variety of
implementations that achieve various subsets of these features. In
particular, we observe that group signature schemes can be used to escrow
identities, achieving most (though not all) of the desired features.
On the Hardness of ApproximationsIn this project, we investigated the hardness of approximation problems. Hardness is typically shown by demonstrating a hard gap for an optimization problem. We refined the complexity analysis of approximation hardness, by relating it to a new parameter called gap location. In particular, it was noted that not only the size of the hard gap matters, but also its location. Many of the results obtained so far for approximations yield the strongest analysis also with respect to this refined parameter, but some known results (e.g. MAX-k-COLORABILITY, MAX 3-DIMENSIONAL MATCHING and MAX NOT-ALL-EQUAL 3SAT) fall short of doing so. A second contribution of our work was in filling the gap in these cases by presenting new hardness reductions. Next, we presented definitions of new approximation versions of some NP-Complete optimization problems. The problems we treated were VERTEX COVER (for which we defined a different optimization problem from the one treated by Papadimitriou and Yannakakis), k-EDGE COLORING, SET SPLITTING, and a restricted version of FEEDBACK VERTEX SET and FEEDBACK ARC SET. We defined all these problems and provided hardness results with the strongest possible gap location.
Data Structures Construction and AnalysisIn this project, we studied ways to rigorously analyze the advantages and disadvantages (or impossibilities) of data structure constructs. In the first study, we considered the use of linear (or affine) transformations between two vector spaces over a finite field F for constructing universal hash functions. A universal hash function is a family of functions, such that choosing one of them at random provides some nice hashing properties. We ask how good linear functions behave in this respect and examine the expected size of the maximal bucket size as a measure for a "good hashing" property. We discover that linear functions over large fields behave quite badly whereas linear functions over small fields behave quite well, and not far from optimal. This study involves some nice linear algebra and in particular, in the course of our proof we develop a tool which may be of independent interest. Suppose we have a subset S of a vector space D over Z2, and consider a random linear mapping of D to a smaller vector space R. If the cardinality of S is larger than cε|R|log|R|, then with probability 1 - ε, the image of S will cover all elements in the range. In a second study, we check the ability of
data structures to hide information that is not expected to be revealed by
the structure. History independent data structures, are data structures that
possess a strong security property: even if an intruder manages to get a
copy of the data structure, the memory layout of the structure yields no
additional information on the history of operations applied on the structure
beyond the information obtainable from the content itself. A stronger
security property is that even if an intruder breaks into the system several
times without being noticed and records the data structure layouts, he can
still obtain no additional information. An open question was whether
these two notions are equally hard to obtain. In this paper we provide a
separation between the two requirements for comparison-based algorithms. We
show very strong lower bounds for obtaining the stronger notion of history
independence for a large class of data structures, including, for example,
the heap and the queue abstract data structures. We also provide
complementary upper bounds showing that the heap abstract data structure may
be made weakly history independent in the comparison based model without
incurring any additional (asymptotic) cost on any of its operations. (A
similar result is easy for the queue.) Thus, we obtain the first separation
between the two notions of history independence. The gap we obtain is
exponential: some operations may be executed in logarithmic time (or even in
constant time) with the weaker definition, but require linear time with the
stronger definition.
|