Changes between Version 17 and Version 18 of workshop
- Timestamp:
- Jul 3, 2014, 10:06:28 AM (4 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
workshop
v17 v18 29 29 ==== Session: Constructive algorithms (9h30-12h30) ==== 30 30 31 '''Session Chair:''' Julien Tesson 32 31 33 * 9h30-10h10: Kiminori Matsuzaki, '''Functional Models of Hadoop !MapReduce and Their Application to Scan'''[[BR]]!MapReduce, first proposed by Google, is a remarkable programming model for processing very large data. An open-source Java implementation of Google’s !MapReduce, Hadoop, is now widely used for developing wide-range of applications. Under these situations, functional models for the !MapReduce computation play important roles in for example understanding the computation, proving the correctness of programs, and even optimization. In this study, we develop five functional models that capture semantics of the !MapReduce computation. In addition, we develop !MapReduce algorithms for the list scan (prefix sums) on the proposed models. With the most concrete model of !MapReduce, we can successfully define the BSP-based scan algorithm. 32 34 … … 34 36 35 37 * 10h50-11h10: '''Coffee Break''' 38 39 '''Session Chair:''' Kiminori Matsuzaki 36 40 37 41 * 11h10-11h50: Reina Miyazaki and Kiminori Matsuzaki, '''Parallel Tree Accumulations on !MapReduce'''[[BR]]!MapReduce is a remarkable parallel programming model as well as a parallel processing infrastructure for large-scale data processing. !MapReduce is now widely available on cloud environments, developing methodology or patterns of !MapReduce programming is important. In particular, XML is the de facto standard for representing data, processing semi-structured data is involved in many applications. The target computational pattern in this paper are tree accumulations. Tree accumulations are shape-preserving computations over trees in which values are updated through flows over the tree. We develop BSP algorithms for two tree accumulations as extensions of the BSP algorithm for tree reduction by Kakehi et al. (2006). We also implemented the two-superstep algorithms by a single !MapReduce execution. Experimental results on 16-node PC cluster show good speedups with factors of 10.9-12.7. … … 43 47 ==== Session: Algorithmic skeleton libraries (14h00-18h00) ==== 44 48 49 '''Session Chair:''' Frédéric Loulergue 50 45 51 * 14h15-15h30 ''Invited Talk'': Joel Falcou, '''Costless Software Abstractions for Parallel Architectures'''[[BR]]Performing large, intensive or non-trivial computing on array like data structures is one of the most common task in scientific computing, video game development and other fields. This matter of fact is backed up by the large number of tools, languages and libraries to perform such tasks. If we restrict ourselves to C++ based solutions, more than a dozen such libraries exists from BLAS/LAPACK C++ binding to template meta-programming based Blitz++ or Eigen. If all of these libraries provide good performance or good abstraction, none of them seems to fit the need of so many different user types. Moreover, as parallel system complexity grows, the need to maintain all those components quickly become unwieldy. This talk explores various software design techniques and their application to the implementation of a parallel computing librariy in such a way that:[[BR]]- abstraction and expressiveness are maximized through the use of Parallel Skeletons[[BR]]- cost over efficiency is minimized thanks to Generative Programming[[BR]]- architecture specific hints are used throughout the whole library thanks to architecture aware tag dispatching[[BR]]We'll skim over various applications and see how they can benefit from such tools. We will conclude by discussing what lessons were learnt from this kind of implementation and how those lessons can translate into new directions for the C++ language itself and for the design of future Parallel Skeletons. 46 52 47 53 * 15h30-16h00: '''Coffee Break''' 54 55 '''Session Chair:''' Julien Tesson 48 56 49 57 * 16h00-16h40: Kento Emoto, Kiminori Matsuzaki, '''The !SkeTo Library'''[[BR]]The !SkeTo (Skeletons in Tokyo) library is a library of algorithmic skeletons, which was originally designed to allow users to describe parallel computations in a sequential manner and implemented in C++ on top of MPI. It provides three distributed data structures for lists (1D-arrays), matrices (2D-arrays) and trees, as well as skeletons for their manipulation. Recent works on the !SkeTo library have been done for its automatic optimization mechanism by using the meta-programming technique with C++ templates. In this talk, we will introduce the outline of our !SkeTo library and show how we integrated the optimization mechanism on the algorithmic skeletons. … … 59 67 60 68 ==== Session: Verified compilation (10h00-12h10) ==== 69 70 '''Session Chair:''' Frédéric Loulergue 61 71 62 72 * 10h00-11h10: ''Invited Speaker'' Francesco Zappa Nardelli, '''We can't get memory models right.''