Document number: N3563

Date: 2013-03-15

C++ Mapreduce

by Chris Mysen, Lawrence Crowl, Adam Berkan

For large scale distributed problems, the map-reduce framework has proven to be a highly effective way at creating highly parallel workflows working over distributed filesystems on petabyte scale operations and has been used for analysis, machine learning, and implementation of many distributed computation problems at Google.

This proposal outlines the details of a version of mapreduce which is logically simple but very extensible, based heavily off of both distributed and threaded versions of mapreduce, allowing for implementations which work as distributed, threaded, or both. There are some simplifications in this implementation which are detailed later, but much of the flexibility of many of the implemented map-reduces is retained.

Document number: N3562

Date: 2013-03-15

Executors and schedulers, revision 1

by Matt Austern, Lawrence Crowl, Chandler Carruth, Niklas Gustafsson, Chris Mysen, Jeffrey Yasskin

This paper is a proposal for executors, objects that can execute units of work packaged as function objects, in the form of an abstract base class and several concrete classes that inherit from it. It is based on components that are heavily used in internal Google and Microsoft code, with changes to better match the style of the C++ standard.

This proposal discusses the design decisions behind the API and also includes a first draft of formal wording for the working paper.

Document number: N3561

Date: 2013-03-15

Semantics of Vector Loops

by Robert Geva, Clark Nelson

In the SG1 conference call on Feb 5 2013, I presented the topic of a critical section in a vector loop. The discussion on the narrow topic itself resulted in the consensus that a critical section in a vector loops is undefined behavior. However, the discussion also led to broader interest in the semantics of a vector loop, which I was asked to present. This paper describes the semantics we propose. Note that this paper is meant as a continuation of earlier papers on vector loops, and is probably not self-contained. It does not repeat the syntax and language rules portions of the proposal.

As was stated in earlier meetings, this proposal is an attempt to codify existing practice in vector programming. While in a narrow sense, there are no existing practices of vector programming within standard C++, vector programming is broadly used in ad hoc ways. The expectations of programmers are well understood. The proposal here is not to invent new programming models. Instead, it is an attempt to codify the existing expectations of existing practitioners using C++ methodology.

Document number: N3557

Date: 2013-03-18

Considering a Fork-Join Parallelism Library

by Pablo Halpern

There is general consensus in the Concurrency and Parallelism study group (SG1) that strict fork-join parallelism would be a desirable feature to add to C++. They asked me to research whether it is possible to create a pure library interface for strict fork-join parallelism that achieves the same benefits as the well-established keyword-based language interface pioneered by the Cilk project and proposed for standardization in N3409. The technical and aesthetic advantages offered by the language approach include simple syntax, appropriate lifetimes for arguments in asynchronous function calls, correct overload resolution for asynchronous function calls, clear and enforceable strictness, and correct exception handling. This paper describes the challenges of creating a comparable library interface and explores the possibility of making small, general-purpose, language changes to enable a library solution to overcome those challenges. Ultimately, however, the library interface shows significant weaknesses when integrating with core features such as object lifetimes and exception scope. The library interface in particular is susceptible to misuses which may introduce subtle problems into programs that would be hard for many programmers to diagnose. Since our goal is making parallel programming accessible to the widest possible range of programmers I question whether a library approach could ever achieve this goal.

Document number: N3556

Date: 2013-03-18

Thread-Local Storage in X-Parallel Computations

by Pablo Halpern, Charles E. Leiserson

... [W]e designate the model under discussion as being an X-parallel model, where X might represent a variety of individual parallelization technologies, including vector units, GPU’s, task-based multithreading, attached processing, and the like. ...

The purpose of this paper is to develop terminology so that the impact of any X-parallel model on TLS can be described clearly and evaluated effectively. We compare the semantics of accessing a TLS variable within an X-parallel region to the semantics of accessing the same variable in serial execution. We propose a 5-level hierarchical taxonomy of TLS concordance, where each level in the hierarchy is more faithful to the way the existing threading model treats TLS than the level below. Placing an X-parallel model lower within the taxonomy does not necessarily mean that it is a bad model, but lower in the hierarchy does mean that an X-parallel model is a less faithful extension to the existing standard than a higher-level model, at least as far as its adherence to legacy TLS behavior is concerned.

We conclude with a brief discussion in which we advocate that any X-parallel model should provide Level-5 (full) concordance — the highest level — unless there is a compelling reason to the contrary.

Document number: N3543

Date: 2013-03-15

Priority Queue, Queue and Stack: Changes and Additions

by Gary Powell, Tim Blechmann

Priority Queues, Stacks and heaps are extremely useful data structures suitable for solving many common ordering problems. C++ 2011 provides only a couple of template adaptor classes; priority_queue, stack and queue, which provide limited functionality. To overcome the current limitations, this paper proposes that new containers be added to the standard library to replace the current adaptors which would then be depreciated. Additionally there are several alternative implementations of heaps having different performance characteristics which should be added to the standard library. Especially, the suggested options for these heaps deal with these additional aspects:

• Iterators: Heaps provide iterators to iterate all elements.
• Mutability: The priority of heap elements can be modified.
• Mergeable: While all heaps can be merged, some can be merged efficiently.
• Stability: Heaps can be configured to be stable sorted.
• Comparison: Heaps can be compared for equivalence.

Document number: N3542

Date: 2013-03-18

Proposal for Unbounded-Precision Integer Types

by Pete Becker

This paper proposes two unbounded-precision integer types. The type integer represents signed integer values. The type bits represents an unbounded set of bit values.

To support interoperability, objects of either type can be constructed from values of any of the standard integer types. So code like this just works:

    integer i = 30000;
    integer j = 1000 * i;

    bits b = 0xFF;
    bits c = b & 0xAA;

Converting a negative number to an object of type bits sets the number to the complement of this initializer, so this code just works:

    bits b = -3; // sets b to ...11111100

Document number: N3539, N3540, N3541

Date: 2013-03-18

C++ Standard Core Language Active Issues, Revision 83

C++ Standard Core Language Defect Reports and Accepted Issues, Revision 83

C++ Standard Core Language Closed Issues, Revision 83

by William M. Miller

The purpose of these documents is to record the disposition of issues that have come before the Core Language Working Group of the ANSI (INCITS PL22.16) and ISO (WG21) C++ Standard Committee.

Document number: N3534

Date: 2013-03-15

C++ Pipelines

by Adam Berkan, Alasdair Mackintosh

We propose a C++ pipeline library that allows application programmers to combine simple data transformations into a complete multithreaded data-processing pipeline. Individual transformation functions are isolated from each other, and may be run in parallel. We use a pipe syntax that should be familiar to users of Unix or Microsoft shells.

(pipeline::from(input_queue) |
  bind(grep, "^Error") |
  bind(vgrep, "[email protected]") |
  bind(sed, "'s/^Error:.*Message: //") |
  output_queue).run(&threadpool);

Document number: N3530

Date: 2013-03-15

Leveraging OpenMP infrastructure for language level parallelisation

by Darryl Gove, Nawal Copty, Michael Wong

This proposal suggests how language level parallelisation can be achieved using the existing OpenMP infrastructure. OpenMP is a mature, well established and widely used specification for writing portable multi-threaded applications on a shared memory system.