 |
Multi-Core Processors  |
| Ben-Gurion University |
Multi-Core Processors Day 2008
Abstracts and Bios
Hopscotch Hashing: a Hash Map for the Multicore Era
Nir Shavit, TAU
Abstract:
We present a new resizable hash table algorithm directed at multicore machines. The algorithm is based on a novel hopscotch multi-phased probing and displacement technique that combines elements of cuckoo hashing and linear probing. The hopscotch technique avoids the double-hash and linear probe overheads of these former algorithms, providing a table with very low synchronization costs and high cache hit ratios.
In a series of benchmarks on a state-of-the-art 64-way Niagara II multicore machine as well as a 4-way Intel multicore, the new algorithm proves to be highly scalable, delivering about 3 times the throughput of today's most efficient concurrent hash algorithm, Lea's ConcurrentHash Map from java.concurr.util. It does so with a memory utilization of over 90%. Perhaps more interestingly, on a single core, a sequential version of Hopscotch outperforms all know sequential hash table algorithms, and by a significant factor as the table density increases beyond 50%.
Joint work with Maurice Herlihy of Brown University and Moran Tzafrir of TAU
Bio:
Nir Shavit received a B.A. and M.Sc. from the Technion and a Ph.D. from the Hebrew University, all in Computer Science. He was a Postdoctoral Researcher at IBM Almaden Research Center, Stanford University, and MIT, and a Visiting Professor at MIT. He joined the Computer Science Department at Tel-Aviv University in 1992, and was at various periods since 1999 a Member of Technical Staff at Sun Microsystems Laboratories. Nir Shavit is the recipient of the Israeli Industry Research Prize in 1993 and the ACM/EATCS Godel Prize in Theoretical Computer Science in 2004.
Nir Shavit designed (together with his students) the first Software Transactional Memory system, and has been involved (together with his students and colleagues) in the design of several of today's state-of-the-art STMs including the recent transactional locking paradigm.
Software Enablement for Multi-Core Architectures
Bilha Mendelson, IBM Haifa Research Lab
Abstract:
A recent trend of transitioning to multi-core architectures in the mainstream market segments creates significant challenges for programming systems. The market need for creating portable multi-threaded applications that exploit high performance of chip multiprocessors is not easily supported by existing programming models and languages, compiler technology, performance analysis and testing tools.
In the talk I will overview various research directions in this area and present some partial results achieved for the Cell and PPC platforms.
Bio:
Dr. Bilha Mendelson is the manager of the Code Optimization and Quality Technologies department in the IBM Haifa Research Lab, Israel. Since joining IBM in 1990, she has been developing optimizations for the DSP compiler and for the AS/400 optimizing translator. She received a B.Sc. and an M.Sc. in Computer Science from the Technion Israel Institute of Technology, and a Ph.D. in Computer Engineering from the University of Massachusetts at Amherst. She also received an MBA from the Haifa University in Israel. She holds several patents primarily in the area of code optimization. Her areas of interest include code optimization algorithms, compiler technology, computer architecture, and performance improvement issues.
Locality in Concurrent Data Structure
Hagit Attiya, Technion
Abstract:
With multi-core and multiprocessing systems becoming widespread, most algorithms and data structures need to accommodate concurrent access; to reap the performance benefits of such systems, this should be done without effectively sequentializing competing operations. We explain the concept of locality and describe two methodologies for designing concurrent data structures so as to decrease interference among operations and increase concurrency and throughput. One methodology specifically addresses doubly-linked lists, while the other deals with generic multi-word operations.
Bio:
Hagit Attiya is a professor of Computer Science at the Technion, Israel Institute of Technology. Her general research interests are in distributed and parallel computation. She received her B.Sc. degree in Mathematics and Computer Science from the Hebrew University of Jerusalem in 1981, her M.Sc .and Ph.D. degrees in Computer Science from the Hebrew University of Jerusalem in 1983 and 1987, respectively.
Industrial and Research Challenges in the Area of Multi-Core and Many Cores
Avi Mendelson, Intel Haifa and Technion
Abstract:
Recently the computer architecture world is shifting toward multi-core and many core systems. This "new" trend already happened in the past with only partial success. As we discuss in the talk, a major part of the past failure was the inability to efficiently use parallel systems. In order to avoid repeating past mistakes, the research community needs to provide essential solutions to critical issues.
In my talk I will provide a short historical perspective on the past similar trends, and highlight a few critical directions that the research must address in order to make the new trend result in greater success.
Bio:
Avi Mendelson is a principal engineer in Intel's Mobile Platform Group in Haifa, Israel, and adjunct professor in the CS and EE departments, Technion—Israel Institute of Technology. He received his B.Sc. and M.Sc. degrees from the Technion, Israel Institute of Technology and his Ph.D. from the University of Massachusetts at Amherst. Avi has been with Intel for 7 years. He started as senior researcher in Intel Labs, later he moved to the Microprocessor group where he served as the CMP architect of Intel Core Duo. Avi's work and research interests are in computer architecture, low power design, parallel systems, OS related issues and virtualization.
Dynamic Asymmetric Management of Large-scale Multi-Cores
Amnon Barak, Hebrew University of Jerusalem
Abstract:
This presentation is about several operating system alternatives for dynamic management of resources in large scale, distributed memory multi-cores (cluster on a chip), with special emphasis on asymmetric systems that can make all the cores perform like a single computer with many processors.
Timing-based Synchronization Algorithms
Gadi Tubenfeld, Interdisciplinary Center in Herzliya (IDC)
Abstract:
Concurrent systems exhibit a significant degree of synchrony in practice, but few guarantee to do so. This synchrony can be exploited to achieve algorithms with properties that are not possible in completely asynchronous systems; however, in general we cannot afford to risk incorrect behavior in case our assumptions about this synchrony are occasionally violated. In this talk we will explored the possible middle ground of exploiting synchrony when it is available, but in any case guaranteeing correctness regardless of the timing behavior of the system.
That is, we will discuss the design of indulgent algorithms which are algorithms that work correctly and efficiently whenever the timing assumptions are satisfied, but never violate their safety properties when these assumptions are not satisfied by the underlying system. The appeal of such algorithms lies in the fact that when they are executed in an asynchronous system, they "lie in wait" for a short period of time during which certain timing constraints are met, and when this happens these algorithms take advantage of the situation and efficiently complete their mission.
Bio:
Gadi Tubenfeld is the dean of the Efi Arazi School of Computer Science at the Interdisciplinary Center in Herzliya. Before joining IDC, he was the head of the computer science division at Israel's Open University; member of technical staff at AT&T Bell Laboratories; consultant to AT&T Labs-Research; and a research scientist and lecturer at Yale University. Gadi holds a Ph.D. in Computer Science from the Technion. His primary research interests are in concurrent and distributed computing.
Scheduling-Based Collision Avoidance and Resolution for Software Transactional Memory
Danny Hendler, Ben-Gurion University
Abstract:
The emergence of multi-core architectures is adding impetus to the shift from single-threaded applications to concurrent, multi-threaded applications. Transactional memory is a concurrent programming abstraction that is viewed by many as having the potential of becoming a superior alternative to lock-based programming for these architectures. We present CAR-STM, a scheduling-based mechanism for Collision Avoidance and Resolution that can be incorporated into existing software transactional memory (STM) implementations. In addition to proactive collision avoidance that is based on application-specific hints, CAR-STM's transaction scheduling supports novel and highly efficient contention managers that resolve transaction conflicts by serializing the execution of colliding transactions. Joint work with Shlomi Dolev and Adi Suissa (both from BGU)
Bio:
Danny Hendler is a lecturer at the Computer Science Department at Ben-Gurion University. He returned to Academy in 2001 after working for almost twenty years in the High-Tech industry in both technical and managerial positions. He received his Ph.D. in Computer Science from Tel-Aviv University in 2004. His research interests include distributed algorithms and lower bounds, dynamic load-balancing and contention-aware metrics and algorithms.