[For complete, up-to-date TBB information visit: http://www.ThreadingBuildingBlocks.org]
INFORMATION IN THIS DOCUMENT IS PROVIDED IN CONNECTION WITH INTEL® PRODUCTS. NO LICENSE, EXPRESS OR IMPLIED, BY ESTOPPEL OR OTHERWISE, TO ANY INTELLECTUAL PROPERTY RIGHTS IS GRANTED BY THIS DOCUMENT. EXCEPT AS PROVIDED IN INTEL'S TERMS AND CONDITIONS OF SALE FOR SUCH PRODUCTS, INTEL ASSUMES NO LIABILITY WHATSOEVER, AND INTEL DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY, RELATING TO SALE AND/OR USE OF INTEL PRODUCTS INCLUDING LIABILITY OR WARRANTIES RELATING TO FITNESS FOR A PARTICULAR PURPOSE, MERCHANTABILITY, OR INFRINGEMENT OF ANY PATENT, COPYRIGHT OR OTHER INTELLECTUAL PROPERTY RIGHT. Intel products are not intended for use in medical, life saving, life sustaining, critical control or safety systems, or in nuclear facility applications. Intel may make changes to specifications and product descriptions at any time, without notice.
Designers must not rely on the absence or characteristics of any features or instructions marked "reserved" or "undefined." Intel reserves these for future definition and shall have no responsibility whatsoever for conflicts or incompatibilities arising from future changes to them.
MPEG is an international standard for video compression/decompression promoted by ISO. Implementations of MPEG CODECs, or MPEG enabled platforms may require licenses from various entities, including Intel Corporation.
The software described in this document may contain software defects which may cause the product to deviate from published specifications. Current characterized software defects are available on request.
This document as well as the software described in it is furnished under license and may only be used or copied in accordance with the terms of the license. The information in this manual is furnished for informational use only, is subject to change without notice, and should not be construed as a commitment by Intel Corporation. Intel Corporation assumes no responsibility or liability for any errors or inaccuracies that may appear in this document or any software that may be provided in association with this document.
Except as permitted by such license, no part of this document may be reproduced, stored in a retrieval system, or transmitted in any form or by any means without the express written consent of Intel Corporation.
Developers must not rely on the absence or characteristics of any features or instructions marked "reserved" or "undefined." Improper use of reserved or undefined features or instructions may cause unpredictable behavior or failure in developer’s software code when running on an Intel processor. Intel reserves these features or instructions for future definition and shall have no responsibility whatsoever for conflicts or incompatibilities arising from their unauthorized use.
BunnyPeople, Celeron, Celeron Inside, Centrino, Centrino logo, Core Inside, FlashFile, i960, InstantIP, Intel, Intel logo, Intel386, Intel486, Intel740, IntelDX2, IntelDX4, IntelSX2, Intel Core, Intel Inside, Intel Inside logo, Intel. Leap ahead., Intel. Leap ahead. logo, Intel NetBurst, Intel NetMerge, Intel NetStructure, Intel SingleDriver, Intel SpeedStep, Intel StrataFlash, Intel Viiv, Intel vPro, Intel XScale, IPLink, Itanium, Itanium Inside, MCS, MMX, Oplus, OverDrive, PDCharm, Pentium, Pentium Inside, skoool, Sound Mark, The Journey Inside, VTune, Xeon, and Xeon Inside are trademarks or registered trademarks of Intel Corporation or its subsidiaries in the United States and other countries.
* Other names and brands may be claimed as the property of others.
Copyright © 2005–2007 Intel Corporation.
Revision History
Document Number
Revision Number
Description
Revision Date
315415-001
1.5
Add Partitioner concept as a preview feature for parallel_for, parallel_reduce and parallel_scan. Add method recycle_as_safe_continuation. Fix missing “Continuation-passing style” figure.
2007-Mar-1
1.6
Fix typographical errors. Fix ParallelMerge example to make is_divisible() const.
2007-May-18
Contents
1 Overview.........................................................................................................1
2 General Conventions.........................................................................................2
2.1 Notation................................................................................................2
2.2 Terminology..........................................................................................3
2.2.1 Concept...................................................................................3
2.2.2 Model......................................................................................3
2.2.3 CopyConstructible.....................................................................4
2.3 Identifiers.............................................................................................4
2.3.1 Case........................................................................................4
2.3.2 Reserved Identifier Prefixes........................................................4
2.4 Namespaces..........................................................................................4
2.4.1 tbb Namespace.........................................................................4
2.4.2 tbb::internal Namespace............................................................5
2.5 Thread Safety........................................................................................5
2.6 Enabling Debugging Features...................................................................5
2.6.1 TBB_DO_ASSERT Macro.............................................................5
2.6.2 TBB_DO_THREADING_TOOLS Macro............................................5
3 Algorithms.......................................................................................................7
3.1 Splittable Concept..................................................................................7
3.1.1 split Class................................................................................8
3.2 Range concept.......................................................................................8
3.2.1 blocked_range<Value> Template Class........................................9
3.2.1.1 size_type.................................................................11
3.2.1.2 blocked_range( Value begin, Value end, size_t grainsize=1 )............................................................................12
3.2.1.3 blocked_range( blocked_range& range, split )...............12
3.2.1.4 size_type size() const................................................12
3.2.1.5 bool empty() const...................................................13
3.2.1.6 size_type grainsize() const.........................................13
3.2.1.7 bool is_divisible() const.............................................13
3.2.1.8 const_iterator begin() const.......................................13
3.2.1.9 const_iterator end() const..........................................13
3.2.2 blocked_range2d Template Class...............................................14
3.2.2.1 row_range_type.......................................................16
3.2.2.2 col_range_type........................................................16
3.2.2.3 blocked_range2d<RowValue,ColValue>( RowValue row_begin, RowValue row_end, typename row_range_type::size_type row_grainsize, ColValue col_begin, ColValue col_end, typename col_range_type::size_type col_grainsize )....................16
3.2.2.4 blocked_range2d<RowValue,ColValue> ( blocked_range2d& range, split ).................................16
3.2.2.5 bool empty() const...................................................17
3.2.2.6 bool is_divisible() const.............................................17
3.2.2.7 const row_range_type& rows() const...........................17
3.2.2.8 const col_range_type& cols() const.............................17
3.3 Preview Feature: Partitioner Concept.......................................................17
3.3.1 simple_partitioner Class.............................................................3
3.3.1.1 simple_partitioner()....................................................3
3.3.1.2 simple_partitioner(simple_partitioner &partitioner, split ).3
3.3.1.3 template<typename Range> bool should_execute_range (const Range &r, const task &t)....................................3
3.3.2 auto_partitioner Class................................................................3
3.3.2.1 auto_partitioner().......................................................4
3.3.2.2 auto_partitioner(auto_partitioner &partitioner, split ).......4
3.3.2.3 template<typename Range> bool should_execute_range (const Range &r, const task &t)....................................4
3.4 parallel_for<Range,Body> Template Function............................................4
3.4.1 Using the Partitioner Preview Feature...........................................8
3.5 parallel_reduce<Range,Body> Template Function.......................................9
3.5.1 Using the Partitioner Preview Feature.........................................12
3.6 parallel_scan<Range,Body> Template Function........................................13
3.6.1 pre_scan_tag and final_scan_tag Classes....................................15
3.6.1.1 bool is_final_scan()...................................................16
3.6.2 Using the Partitioner Preview Feature.........................................16
3.7 parallel_while Template Class.................................................................18
3.7.1 parallel_while<Body>()............................................................19
3.7.2 ~parallel_while<Body>().........................................................19
3.7.3 Template <typename Stream> void run( Stream& stream, const Body& body )..........................................................................19
3.7.4 void add( const value_type& item )............................................19
3.8 pipeline Class......................................................................................20
3.8.1 pipeline()...............................................................................21
3.8.2 ~pipeline().............................................................................21
3.8.3 void add_filter( filter& f )..........................................................21
3.8.4 void run( size_t max_number_of_live_tokens )............................21
3.8.5 void clear()............................................................................21
3.8.6 filter Class..............................................................................22
3.8.6.1 filter( bool is_serial ).................................................22
3.8.6.2 ~filter()...................................................................22
3.8.6.3 bool is_serial() const.................................................23
3.8.6.4 virtual void* operator()( void * item )..........................23
3.9 parallel_sort<RandomAccessIterator, Compare> Template Function............23
4 Containers.....................................................................................................25
4.1 concurrent_hash_map<Key,T,HashCompare> Template Class....................25
4.1.1 Whole Table Operations...........................................................27
4.1.1.1 concurrent_hash_map()............................................27
4.1.1.2 concurrent_hash_map( const concurrent_hash_map& table ).....................................................................27
4.1.1.3 ~concurrent_hash_map()..........................................27
4.1.1.4 concurrent_hash_map& operator= ( concurrent_hash_map& source ).................................27
4.1.1.5 void clear()..............................................................27
4.1.2 Concurrent Access...................................................................28
4.1.2.1 const_accessor.........................................................28
4.1.2.2 accessor..................................................................30
4.1.3 Concurrent Operations.............................................................30
4.1.3.1 bool find( const_accessor& result, const Key& key ) const31
4.1.3.2 bool find( accessor& result, const Key& key )................31
4.1.3.3 bool insert( const_accessor& result, const Key& key )....31
4.1.3.4 bool insert( accessor& result, const Key& key ).............32
4.1.3.5 bool erase(const Key& key ).......................................32
4.1.4 Parallel Iteration.....................................................................32
4.1.4.1 const_range_type range( size_t grainsize ) const..........32
4.1.4.2 range_type range( size_t grainsize )............................33
4.1.5 Capacity................................................................................33
4.1.5.1 size_type size() const................................................33
4.1.5.2 bool empty() const...................................................33
4.1.5.3 size_type max_size() const........................................33
4.1.6 Iterators................................................................................33
4.1.6.1 iterator begin().........................................................33
4.1.6.2 iterator end()...........................................................33
4.1.6.3 const_iterator begin() const.......................................34
4.1.6.4 const_iterator end() const..........................................34
4.2 concurrent_queue<T> Template Class....................................................34
4.2.1 concurrent_queue().................................................................36
4.2.2 ~concurrent_queue()...............................................................36
4.2.3 void push( const T& source ).....................................................36
4.2.4 void pop( T& destination )........................................................36
4.2.5 bool pop_if_present( T& destination ).........................................36
4.2.6 size_type size() const..............................................................36
4.2.7 bool empty() const..................................................................37
4.2.8 size_type capacity()................................................................37
4.2.9 void set_capacity( size_type capacity ).......................................37
4.2.10 Iterators................................................................................37
4.2.10.1 iterator begin().........................................................38
4.2.10.2 iterator end()...........................................................38
4.2.10.3 const_iterator begin() const.......................................38
4.2.10.4 const_iterator end() const..........................................38
4.3 concurrent_vector................................................................................38
4.3.1 Whole Vector Operations..........................................................39
4.3.1.1 concurrent_vector()..................................................40
4.3.1.2 concurrent_vector( const concurrent_vector& src )........40
4.3.1.3 concurrent_vector& operator=( const concurrent_vector& src ).......................................................................40
4.3.1.4 ~concurrent_vector()................................................40
4.3.1.5 void clear()..............................................................40
4.3.2 Concurrent Operations.............................................................40
4.3.2.1 size_type grow_by( size_type delta )...........................40
4.3.2.2 void grow_to_at_least( size_type n )...........................41
4.3.2.3 size_t push_back( const_reference value );..................41
4.3.2.4 reference operator[]( size_type index )........................41
4.3.2.5 const_reference operator[]( size_type index ) const;.....41
4.3.3 Parallel Iteration.....................................................................41
4.3.3.1 range_type range( size_t grainsize )............................42
4.3.3.2 const_range_type range( size_t grainsize ) const..........42
4.3.4 Capacity................................................................................42
4.3.4.1 size_type size() const................................................42
4.3.4.2 bool empty() const...................................................42
4.3.4.3 size_type capacity() const..........................................42
4.3.4.4 void reserve( size_type n ).........................................42
4.3.4.5 size_type max_size() const........................................43
4.3.5 Iterators................................................................................43
4.3.5.1 iterator begin().........................................................43
4.3.5.2 iterator end()...........................................................43
4.3.5.3 const_iterator begin() const.......................................43
4.3.5.4 const_iterator end() const..........................................43
4.3.5.5 iterator rbegin().......................................................43
4.3.5.6 iterator rend()..........................................................43
4.3.5.7 const_reverse_iterator rbegin() const..........................44
4.3.5.8 const_ reverse_iterator rend() const............................44
5 Memory Allocation...........................................................................................45
5.1 Allocator Concept.................................................................................45
5.2 scalable_allocator<T> Template Class.....................................................46
5.3 cache_aligned_allocator<T> Template Class............................................47
5.3.1 pointer allocate( size_type n, void* hint=0 )...............................49
5.3.2 void deallocate( pointer p, size_type n ).....................................49
5.3.3 char* _Charalloc( size_type size )..............................................49
5.4 aligned_space Template Class................................................................50
5.4.1 aligned_space()......................................................................50
5.4.2 ~aligned_space()....................................................................50
5.4.3 T* begin()..............................................................................51
5.4.4 T* end()................................................................................51
6 Synchronization..............................................................................................52
6.1 Mutexes..............................................................................................52
6.1.1 Mutex Concept........................................................................52
6.1.2 mutex Class...........................................................................53
6.1.3 spin_mutex Class....................................................................54
6.1.4 queuing_mutex Class...............................................................54
6.1.5 ReaderWriterMutex Concept......................................................55
6.1.5.1 ReaderWriterMutex().................................................56
6.1.5.2 ~ReaderWriterMutex()..............................................56
6.1.5.3 ReaderWriterMutex::scoped_lock()..............................56
6.1.5.4 ReaderWriterMutex::scoped_lock( ReaderWriterMutex& rw, bool write =true).................................................56
6.1.5.5 ReaderWriterMutex::~scoped_lock()...........................56
6.1.5.6 void ReaderWriterMutex:: scoped_lock:: acquire( ReaderWriterMutex& rw, bool write=true )..................56
6.1.5.7 bool ReaderWriterMutex:: scoped_lock::try_acquire( ReaderWriterMutex& rw, bool write=true )..................57
6.1.5.8 void ReaderWriterMutex:: scoped_lock::release()..........57
6.1.5.9 bool ReaderWriterMutex:: scoped_lock::upgrade_to_writer()...............................57
6.1.5.10 bool ReaderWriterMutex:: scoped_lock::downgrade_to_reader()..........................57
6.1.6 spin_rw_mutex Class...............................................................57
6.1.7 queuing_rw_mutex Class..........................................................58
6.2 atomic<T> Template Class....................................................................59
6.2.1 enum memory_semantics.........................................................60
6.2.2 value_type fetch_and_add( value_type addend ).........................61
6.2.3 value_type fetch_and_increment().............................................61
6.2.4 value_type fetch_and_decrement()............................................61
6.2.5 value_type compare_and_swap.................................................61
6.2.6 Effect....................................................................................61
6.2.7 value_type fetch_and_store( value_type new_value )...................62
8.3.7.2 task* parent() const..................................................84
8.3.7.3 bool is_stolen_task() const.........................................84
8.3.8 task Debugging.......................................................................84
8.3.8.1 state_type state() const............................................85
8.3.8.2 int ref_count() const.................................................86
8.4 empty_task Class.................................................................................87
8.5 task_list Class......................................................................................87
8.5.1 task_list()..............................................................................88
8.5.2 ~task_list()............................................................................88
8.5.3 bool empty() const..................................................................88
8.5.4 push_back( task& task )...........................................................88
8.5.5 task& task pop_front().............................................................88
8.5.6 void clear()............................................................................89
8.6 Catalog of Recommended task Recurrence Patterns...................................89
8.6.1 Blocking Style With k Children...................................................89
8.6.2 Continuation-Passing Style With k Children.................................90
8.6.2.1 Recycling Parent as Continuation................................90
8.6.2.2 Recycling Parent as a Child........................................90
9 References.....................................................................................................92
[For complete, up-to-date TBB information visit: http://www.ThreadingBuildingBlocks.org]