taskflow/taskflow/core/flow_builder.hpp at master · taskflow/taskflow · GitHub

History

2083 lines (1648 loc) · 67.5 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

528

529

530

531

532

533

534

535

536

537

538

539

540

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

571

572

573

574

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

647

648

649

650

651

652

653

654

655

656

657

658

659

660

661

662

663

664

665

666

667

668

669

670

671

672

673

674

675

676

677

678

679

680

681

682

683

684

685

686

687

688

689

690

691

692

693

694

695

696

697

698

699

700

701

702

703

704

705

706

707

708

709

710

711

712

713

714

715

716

717

718

719

720

721

722

723

724

725

726

727

728

729

730

731

732

733

734

735

736

737

738

739

740

741

742

743

744

745

746

747

748

749

750

751

752

753

754

755

756

757

758

759

760

761

762

763

764

765

766

767

768

769

770

771

772

773

774

775

776

777

778

779

780

781

782

783

784

785

786

787

788

789

790

791

792

793

794

795

796

797

798

799

800

801

802

803

804

805

806

807

808

809

810

811

812

813

814

815

816

817

818

819

820

821

822

823

824

825

826

827

828

829

830

831

832

833

834

835

836

837

838

839

840

841

842

843

844

845

846

847

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

864

865

866

867

868

869

870

871

872

873

874

875

876

877

878

879

880

881

882

883

884

885

886

887

888

889

890

891

892

893

894

895

896

897

898

899

900

901

902

903

904

905

906

907

908

909

910

911

912

913

914

915

916

917

918

919

920

921

922

923

924

925

926

927

928

929

930

931

932

933

934

935

936

937

938

939

940

941

942

943

944

945

946

947

948

949

950

951

952

953

954

955

956

957

958

959

960

961

962

963

964

965

966

967

968

969

970

971

972

973

974

975

976

977

978

979

980

981

982

983

984

985

986

987

988

989

990

991

992

993

994

995

996

997

998

999

1000

#pragma once

#include "task.hpp"

#include "../algorithm/partitioner.hpp"

/**

@file flow_builder.hpp

@brief flow builder include file

namespace tf {

// ------------------------------------------------------------------------------------------------

// Concept

// ------------------------------------------------------------------------------------------------

/**

@brief concept to check if a unary operation is valid

@tparam C Callable type.

@tparam B Input iterator-like type.

Satisfied by a callable that can be invoked with the value obtained from

dereferencing an input-like iterator.

Specifically, the following expression must be valid:

@code{.cpp}

c(*b);

@endcode

template <typename C, typename B>

concept UnaryOperationLike =

requires(C c, B b) {

c(*b);

};

/**

@brief concept to check if a binary operation is valid

@tparam C Callable type.

@tparam B1 First input iterator-like type.

@tparam B2 Second input iterator-like type.

Satisfied by a callable that can be invoked with values obtained from

dereferencing two input-like iterators.

Specifically, the following expression must be valid:

@code{.cpp}

c(*b1, *b2);

@endcode

template <typename C, typename B1, typename B2>

concept BinaryOperationLike =

requires(C c, B1 b1, B2 b2) {

c(*b1, *b2);

};

/**

@brief concept to check if a unary transformation operation is valid

@tparam C Callable type.

@tparam B Input iterator type.

@tparam O Output iterator type.

Satisfied by a callable that accepts the value referenced by an input

iterator and produces a result assignable through an output iterator.

Specifically, the following expression must be valid:

@code{.cpp}

*o = c(*b);

@endcode

template <typename C, typename B, typename O>

concept UnaryTransformLike =

requires(C c, B b, O o) {

*o = c(*b);

};

/**

@brief concept to check if a binary transformation operation is valid

@tparam C Callable type.

@tparam B1 First input iterator type.

@tparam B2 Second input iterator type.

@tparam O Output iterator type.

Satisfied by a callable that accepts the values referenced by two input

iterators and produces a result assignable through an output iterator.

Specifically, the following expression must be valid:

@code

*o = c(*b1, *b2);

@endcode

template <typename C, typename B1, typename B2, typename O>

concept BinaryTransformLike =

requires(C c, B1 b1, B2 b2, O o) {

*o = c(*b1, *b2);

};

// ------------------------------------------------------------------------------------------------

// FlowBuilder

// ------------------------------------------------------------------------------------------------

/**

@class FlowBuilder

@brief class to build a task dependency graph

The class provides essential methods to construct a task dependency graph

from which tf::Taskflow and tf::Subflow are derived.

class FlowBuilder {

friend class Executor;

public:

/**

@brief constructs a flow builder with a graph

FlowBuilder(Graph& graph);

/**

@brief creates a static task

@tparam C callable type satisfying tf::StaticTaskLike

@param callable callable to construct a static task

@return a tf::Task handle

The following example creates a static task.

@code{.cpp}

tf::Task static_task = taskflow.emplace([](){});

@endcode

@note

Please refer to @ref StaticTasking for details.

template <StaticTaskLike C>

Task emplace(C&& callable);

/**

@brief creates a runtime task

@tparam C callable type satisfying tf::RuntimeTaskLike

@param callable callable to construct a runtime task

@return a tf::Task handle

The following example creates a runtime task.

@code{.cpp}

tf::Task static_task = taskflow.emplace([](tf::Runtime&){});

@endcode

@note

Please refer to @ref RuntimeTasking for details.

template <RuntimeTaskLike C>

Task emplace(C&& callable);

/**

@brief creates a dynamic task

@tparam C callable type satisfying tf::SubflowTaskLike

@param callable callable to construct a dynamic task

@return a tf::Task handle

The following example creates a dynamic task (tf::Subflow)

that spawns two static tasks.

@code{.cpp}

tf::Task dynamic_task = taskflow.emplace([](tf::Subflow& sf){

tf::Task static_task1 = sf.emplace([](){});

tf::Task static_task2 = sf.emplace([](){});

});

@endcode

@note

Please refer to @ref SubflowTasking for details.

template <SubflowTaskLike C>

Task emplace(C&& callable);

/**

@brief creates a condition task

@tparam C callable type satisfying tf::ConditionTaskLike

@param callable callable to construct a condition task

@return a tf::Task handle

The following example creates an if-else block using one condition task

and three static tasks.

@code{.cpp}

tf::Taskflow taskflow;

auto [init, cond, yes, no] = taskflow.emplace(

[] () { },

[] () { return 0; },

[] () { std::cout << "yes\n"; },

[] () { std::cout << "no\n"; }

);

// executes yes if cond returns 0, or no if cond returns 1

cond.precede(yes, no);

cond.succeed(init);

@endcode

@note

Please refer to @ref ConditionalTasking for details.

template <ConditionTaskLike C>

Task emplace(C&& callable);

/**

@brief creates a multi-condition task

@tparam C callable type satisfying tf::MultiConditionTaskLike

@param callable callable to construct a multi-condition task

@return a tf::Task handle

The following example creates a multi-condition task that selectively

jumps to two successor tasks.

@code{.cpp}

tf::Taskflow taskflow;

auto [init, cond, branch1, branch2, branch3] = taskflow.emplace(

[] () { },

[] () { return tf::SmallVector{0, 2}; },

[] () { std::cout << "branch1\n"; },

[] () { std::cout << "branch2\n"; },

[] () { std::cout << "branch3\n"; }

);

// executes branch1 and branch3 when cond returns 0 and 2

cond.precede(branch1, branch2, branch3);

cond.succeed(init);

@endcode

@note

Please refer to @ref ConditionalTasking for details.

template <MultiConditionTaskLike C>

Task emplace(C&& callable);

/**

@brief creates multiple tasks from a list of callable objects

@tparam C callable types

@param callables one or multiple callable objects constructible from each task category

@return a tf::Task handle

The method returns a tuple of tasks each corresponding to the given

callable target. You can use structured binding to get the return tasks

one by one.

The following example creates four static tasks and assign them to

@c A, @c B, @c C, and @c D using structured binding.

@code{.cpp}

auto [A, B, C, D] = taskflow.emplace(

[] () { std::cout << "A"; },

[] () { std::cout << "B"; },

[] () { std::cout << "C"; },

[] () { std::cout << "D"; }

);

@endcode

template <typename... C> requires (sizeof...(C) > 1)

auto emplace(C&&... callables);

/**

@brief removes a task from a taskflow

@param task task to remove

Removes a task and its input and output dependencies from the graph

associated with the flow builder.

If the task does not belong to the graph, nothing will happen.

@code{.cpp}

tf::Task A = taskflow.emplace([](){ std::cout << "A"; });

tf::Task B = taskflow.emplace([](){ std::cout << "B"; });

tf::Task C = taskflow.emplace([](){ std::cout << "C"; });

tf::Task D = taskflow.emplace([](){ std::cout << "D"; });

A.precede(B, C, D);

// erase A from the taskflow and its dependencies to B, C, and D

taskflow.erase(A);

@endcode

void erase(Task task);

/**

@brief creates a module task for the target object

@tparam T type satisfying tf::GraphLike

@param object a custom object that defines the method @c T::graph()

@return a tf::Task handle

The example below demonstrates a taskflow composition using

the @c composed_of method.

@code{.cpp}

tf::Taskflow t1, t2;

t1.emplace([](){ std::cout << "t1"; });

// t2 is partially composed of t1

tf::Task comp = t2.composed_of(t1);

tf::Task init = t2.emplace([](){ std::cout << "t2"; });

init.precede(comp);

@endcode

The taskflow object @c t2 is composed of another taskflow object @c t1,

preceded by another static task @c init.

When taskflow @c t2 is submitted to an executor,

@c init will run first and then @c comp which spawns its definition

in taskflow @c t1.

The target @c object being composed must define the method

<tt>T::graph()</tt> that returns a reference to a graph object of

type tf::Graph such that it can interact with the executor.

For example:

@code{.cpp}

// custom struct

struct MyObj {

tf::Graph graph;

MyObj() {

tf::FlowBuilder builder(graph);

tf::Task task = builder.emplace([](){

std::cout << "a task\n"; // static task

});

}

Graph& graph() { return graph; }

};

MyObj obj;

tf::Task comp = taskflow.composed_of(obj);

@endcode

Or, simply expose the graph object and pass it to `composed_of`:

@code{.cpp}

tf::Graph graph;

tf::FlowBuilder builder(graph);

tf::Task task = builder.emplace([](){

std::cout << "a task\n"; // static task

});

tf::Task comp = taskflow.composed_of(graph);

@endcode

@note

Please refer to @ref ComposableTasking for details.

template <GraphLike T>

Task composed_of(T& object);

/**

@brief creates a module task from a graph by taking over its ownership

@param graph the graph to adopt (moved into the task)

@return a Task handle to the adopted module task

Unlike tf::FlowBuilder::composed_of, which references an externally-owned

tf::Taskflow, @c adopt transfers ownership of the given tf::Graph into

the task. The graph's lifetime is managed by the executor once adopted,

and the caller has no access to the moved-from graph afterward.

@code{.cpp}

tf::Taskflow taskflow;

tf::Graph g;

tf::FlowBuilder{g}.emplace([]{ std::cout << "task in adopted graph\n"; });

taskflow.adopt(std::move(g)).name("adopted");

@endcode

@note Please refer to @ref ComposableTasking for details.

Task adopt(Graph&& graph);

/**

@brief creates a module task for the target object (convenience overload of tf::FlowBuilder::composed_of)

@tparam T type satisfying tf::GraphLike

@param object a custom object that defines the method @c T::graph()

@return a tf::Task handle

This overload lets you create a module task through the same @c emplace

call you already use for static, runtime, subflow, and condition tasks,

instead of reaching for the differently-named @c composed_of.

It is equivalent to calling tf::FlowBuilder::composed_of(object) and

references the externally-owned graph of @c object, so the caller remains

responsible for keeping @c object alive for as long as the resulting task

may run.

@code{.cpp}

tf::Taskflow t1, t2;

t1.emplace([](){ std::cout << "t1"; });

// equivalent to: tf::Task comp = t2.composed_of(t1);

tf::Task comp = t2.emplace(t1);

@endcode

@note

Please refer to @ref ComposableTasking for details.

template <GraphLike T>

Task emplace(T& object);

/**

@brief creates a module task from a graph by taking over its ownership

(convenience overload of tf::FlowBuilder::adopt)

@param graph the graph to adopt (moved into the task)

@return a Task handle to the adopted module task

This overload lets you create an adopted module task through the same

@c emplace call you already use for other task types, instead of reaching

for the differently-named @c adopt.

It is equivalent to calling tf::FlowBuilder::adopt(std::move(graph)) and

transfers ownership of @c graph into the task; the caller has no access

to the moved-from graph afterward.

@code{.cpp}

tf::Taskflow taskflow;

tf::Graph g;

tf::FlowBuilder{g}.emplace([]{ std::cout << "task in adopted graph\n"; });

// equivalent to: taskflow.adopt(std::move(g)).name("adopted");

taskflow.emplace(std::move(g)).name("adopted");

@endcode

@note Please refer to @ref ComposableTasking for details.

Task emplace(Graph&& graph);

/**

@brief creates a placeholder task

@return a tf::Task handle

A placeholder task maps to a node in the taskflow graph, but

it does not have any callable work assigned yet.

A placeholder task is different from an empty task handle that

does not point to any node in a graph.

@code{.cpp}

// create a placeholder task with no callable target assigned

tf::Task placeholder = taskflow.placeholder();

assert(placeholder.empty() == false && placeholder.has_work() == false);

// create an empty task handle

tf::Task task;

assert(task.empty() == true);

// assign the task handle to the placeholder task

task = placeholder;

assert(task.empty() == false && task.has_work() == false);

@endcode

Task placeholder();

/**

@brief adds adjacent dependency links to a linear list of tasks

@param tasks a vector of tasks

This member function creates linear dependencies over a vector of tasks.

@code{.cpp}

tf::Task A = taskflow.emplace([](){ std::cout << "A"; });

tf::Task B = taskflow.emplace([](){ std::cout << "B"; });

tf::Task C = taskflow.emplace([](){ std::cout << "C"; });

tf::Task D = taskflow.emplace([](){ std::cout << "D"; });

std::vector<tf::Task> tasks {A, B, C, D}

taskflow.linearize(tasks); // A->B->C->D

@endcode

void linearize(std::vector<Task>& tasks);

/**

@brief adds adjacent dependency links to a linear list of tasks

@param tasks an initializer list of tasks

This member function creates linear dependencies over a list of tasks.

@code{.cpp}

tf::Task A = taskflow.emplace([](){ std::cout << "A"; });

tf::Task B = taskflow.emplace([](){ std::cout << "B"; });

tf::Task C = taskflow.emplace([](){ std::cout << "C"; });

tf::Task D = taskflow.emplace([](){ std::cout << "D"; });

taskflow.linearize({A, B, C, D}); // A->B->C->D

@endcode

void linearize(std::initializer_list<Task> tasks);

// ------------------------------------------------------------------------

// parallel iterations

// ------------------------------------------------------------------------

/**

@brief constructs an STL-styled parallel-for task

@tparam B beginning iterator type satisfying tf::InputIteratorLike

@tparam E ending iterator type satisfying tf::InputIteratorLike

@tparam C callable type

@tparam P type satisfying tf::PartitionerLike

@param first iterator to the beginning (inclusive)

@param last iterator to the end (exclusive)

@param callable callable object to apply to the dereferenced iterator

@param part partitioning algorithm to schedule parallel iterations

@return a tf::Task handle

The task spawns asynchronous tasks that applies the callable object to each object

obtained by dereferencing every iterator in the range <tt>[first, last)</tt>.

This method is equivalent to the parallel execution of the following loop:

@code{.cpp}

for(auto itr=first; itr!=last; itr++) {

callable(*itr);

}

@endcode

Iterators can be made stateful by using std::reference_wrapper

The callable needs to take a single argument of

the dereferenced iterator type.

@note

Please refer to @ref ParallelIterations for details.

template <InputIteratorLike B, InputIteratorLike E, typename C, PartitionerLike P = DefaultPartitioner>

requires UnaryOperationLike<C, std::decay_t<std::unwrap_ref_decay_t<B>>>

Task for_each(B first, E last, C callable, P part = P());

/**

@brief constructs an index-based parallel-for task

@tparam B beginning index type (must be integral)

@tparam E ending index type (must be integral)

@tparam S step type (must be integral)

@tparam C callable type

@tparam P type satisfying tf::PartitionerLike

@param first index of the beginning (inclusive)

@param last index of the end (exclusive)

@param step step size

@param callable callable object to apply to each valid index

@param part partitioning algorithm to schedule parallel iterations

@return a tf::Task handle

The task spawns asynchronous tasks that applies the callable object to each index

in the range <tt>[first, last)</tt> with the step size.

This method is equivalent to the parallel execution of the following loop:

@code{.cpp}

// case 1: step size is positive

for(auto i=first; i<last; i+=step) {

callable(i);

}

// case 2: step size is negative

for(auto i=first, i>last; i+=step) {

callable(i);

}

@endcode

Iterators can be made stateful by using std::reference_wrapper

The callable needs to take a single argument of the integral index type.

@note

Please refer to @ref ParallelIterations for details.

template <typename B, typename E, typename S, typename C, PartitionerLike P = DefaultPartitioner>

Task for_each_index(B first, E last, S step, C callable, P part = P());

/**

@brief constructs a parallel-for task over a one- or multi-dimensional index range

@tparam R type satisfying tf::IndexRangesLike (i.e., tf::IndexRanges<T, N>);

for @c N == 1 (equivalently, @c R is tf::IndexRange<T>) the engine

uses the 1D unraveling fast path described below, and for @c N > 1

it partitions the Cartesian product as described further down

@tparam C callable type that is invocable with a single argument of type R

@tparam P type satisfying tf::PartitionerLike

@param range index range

@param callable callable object to apply to each partitioned index range

@param part partitioning algorithm to schedule parallel iterations

@return a tf::Task handle

The task spawns asynchronous tasks that partition @c range and invoke

@c callable once per partition, where each partition is itself a (sub-)range

of the same type @c R.

@par One-dimensional range (`N` == 1)

For a 1D range <tt>tf::IndexRange<T></tt>, the task applies @c callable to

each index subrange of <tt>[first, last)</tt> with the given step size. This

is equivalent to the parallel execution of the following loop:

@code{.cpp}

// case 1: step size is positive

for(auto i=first; i<last; i+=step) {

callable(i);

}

// case 2: step size is negative

for(auto i=first; i>last; i+=step) {

callable(i);

}

@endcode

@code{.cpp}

// [0, 17) with a step size of 2 using tf::IndexRange

tf::IndexRange<int> range(0, 17, 2);

// parallelize the sequence [0, 2, 4, 6, 8, 10, 12, 14, 16]

taskflow.for_each_by_index(range, [](tf::IndexRange<int> subrange) {

// iterate each index in the subrange

for(int i=subrange.begin(); i<subrange.end(); i+=subrange.step_size()) {

printf("iterate %d\n", i);

}

});

executor.run(taskflow).wait();

@endcode

@par Multi-dimensional ranges (`N` > 1)

For @c N > 1, the function parallelises iteration over the Cartesian product

of @c N independent 1D ranges. The total iteration space is linearized in

row-major order (last dimension varies fastest) and divided among workers

according to @c part. Each worker receives one or more orthogonal sub-boxes

and invokes @c callable once per sub-box.

Each sub-box is guaranteed to be a valid hyper-rectangle: every dimension of

the sub-box lies entirely within the corresponding dimension of @c range and

preserves its original step size, including negative strides. Each

dimension of a tf::IndexRanges is a <tt>std::tuple<T, T, T></tt> of

(begin, end, step) accessible through @c dim(d), so the callable typically

destructures it via structured bindings and must iterate the sub-box using

the step sizes reported by each dimension:

@code{.cpp}

// 3D range: depth x height x width

tf::IndexRanges<int, 3> range(

tf::IndexRange<int>(0, D, 1),

tf::IndexRange<int>(0, H, 1),

tf::IndexRange<int>(0, W, 1)

);

taskflow.for_each_by_index(range, [](const tf::IndexRanges<int, 3>& sub) {

auto [d0, d1, ds] = sub.dim(0);

auto [h0, h1, hs] = sub.dim(1);

auto [w0, w1, ws] = sub.dim(2);

for(auto d = d0; d < d1; d += ds) {

for(auto h = h0; h < h1; h += hs) {

for(auto w = w0; w < w1; w += ws) {

// process element (d, h, w)

}

});

@endcode

<b>Stateful ranges</b>

Ranges of any rank can be made stateful by passing them through

@c std::reference_wrapper (via @c std::ref). This is useful when the range

bounds are not known at task-graph construction time. An upstream task must

set the bounds before this task runs:

@code{.cpp}

tf::IndexRanges<int, 2> range;

auto init = taskflow.emplace([&](){

range.dim(0) = {0, rows, 1};

range.dim(1) = {0, cols, 1};

});

auto loop = taskflow.for_each_by_index(std::ref(range), callable);

init.precede(loop);

@endcode

The loop condition inside the callable must respect the sign of each

dimension's step size: use @c < for positive steps and @c > for negative steps.

@note

Please refer to @ref ParallelIterations for details.

template <IndexRangesLike R, typename C, PartitionerLike P = DefaultPartitioner>

Task for_each_by_index(R range, C callable, P part = P());

// ------------------------------------------------------------------------

// transform

// ------------------------------------------------------------------------

/**

@brief constructs a parallel-transform task

@tparam B beginning input iterator type (satisfying tf::InputIteratorLike)

@tparam E ending input iterator type (satisfying tf::InputIteratorLike))

@tparam O output iterator type

@tparam C callable type

@tparam P type satisfying tf::PartitionerLike

@param first1 iterator to the beginning of the first range

@param last1 iterator to the end of the first range

@param d_first iterator to the beginning of the output range

@param c an unary callable to apply to dereferenced input elements

@param part partitioning algorithm to schedule parallel iterations

@return a tf::Task handle

The task spawns asynchronous tasks that applies the callable object to an

input range and stores the result in another output range.

This method is equivalent to the parallel execution of the following loop:

@code{.cpp}

while (first1 != last1) {

*d_first++ = c(*first1++);

}

@endcode

Iterators can be made stateful by using std::reference_wrapper

The callable needs to take a single argument of the dereferenced

iterator type.

@note

Please refer to @ref ParallelTransforms for details.

template <InputIteratorLike B, InputIteratorLike E, typename O, typename C,

PartitionerLike P = DefaultPartitioner>

requires UnaryTransformLike<

std::decay_t<std::unwrap_ref_decay_t<B>>,

std::decay_t<std::unwrap_ref_decay_t<O>>

Task transform(B first1, E last1, O d_first, C c, P part = P());

/**

@brief constructs a parallel-transform task

@tparam B1 beginning input iterator type for the first input range (satisfying tf::InputIteratorLike)

@tparam E1 ending input iterator type for the first input range (satisfying tf::InputIteratorLike)

@tparam B2 beginning input iterator type for the first second range (satisfying tf::InputIteratorLike)

@tparam O output iterator type

@tparam C callable type

@tparam P type satisfying tf::PartitionerLike

@param first1 iterator to the beginning of the first input range

@param last1 iterator to the end of the first input range

@param first2 iterator to the beginning of the second input range

@param d_first iterator to the beginning of the output range

@param c a binary operator to apply to dereferenced input elements

@param part partitioning algorithm to schedule parallel iterations

@return a tf::Task handle

The task spawns asynchronous tasks that applies the callable object to two

input ranges and stores the result in another output range.

This method is equivalent to the parallel execution of the following loop:

@code{.cpp}

while (first1 != last1) {

*d_first++ = c(*first1++, *first2++);

}

@endcode

Iterators can be made stateful by using std::reference_wrapper

The callable needs to take two arguments of dereferenced elements

from the two input ranges.

@note

Please refer to @ref ParallelTransforms for details.

template <InputIteratorLike B1, InputIteratorLike E1, InputIteratorLike B2, typename O, typename C,

PartitionerLike P = DefaultPartitioner>

requires BinaryTransformLike<

std::decay_t<std::unwrap_ref_decay_t<B1>>,

std::decay_t<std::unwrap_ref_decay_t<B2>>,

std::decay_t<std::unwrap_ref_decay_t<O>>

Task transform(B1 first1, E1 last1, B2 first2, O d_first, C c, P part = P());

// ------------------------------------------------------------------------

// reduction

// ------------------------------------------------------------------------

/**

@brief constructs an STL-styled parallel-reduction task

@tparam B beginning iterator type (satisfying tf::InputIteratorLike)

@tparam E ending iterator type (satisfying tf::InputIteratorLike)

@tparam T result type

@tparam O binary reducer type

@tparam P type satisfying tf::PartitionerLike

@param first iterator to the beginning (inclusive)

@param last iterator to the end (exclusive)

@param init initial value of the reduction and the storage for the reduced result

@param bop binary operator that will be applied

@param part partitioning algorithm to schedule parallel iterations

@return a tf::Task handle

The task spawns asynchronous tasks to perform parallel reduction over @c init

and the elements in the range <tt>[first, last)</tt>.

The reduced result is store in @c init.

This method is equivalent to the parallel execution of the following loop:

@code{.cpp}

for(auto itr=first; itr!=last; itr++) {

init = bop(init, *itr);

}

@endcode

Iterators can be made stateful by using std::reference_wrapper

@note

Please refer to @ref ParallelReduction for details.

template <InputIteratorLike B, InputIteratorLike E, typename T, typename O, PartitionerLike P = DefaultPartitioner>

Task reduce(B first, E last, T& init, O bop, P part = P());

/**

@brief constructs an index range-based parallel-reduction task over a

one- or multi-dimensional index range

@tparam R type satisfying tf::IndexRangesLike (i.e., tf::IndexRanges<T, N>);

for @c N == 1 (equivalently, @c R is tf::IndexRange<T>) @c lop

receives a 1D subrange as described below, and for @c N > 1 it

receives a sub-box of the Cartesian product, mirroring

tf::FlowBuilder::for_each_by_index

@tparam T result type

@tparam L local reducer type

@tparam G global reducer type

@tparam P type satisfying tf::PartitionerLike

@param range index range

@param init initial value of the reduction and the storage for the reduced result

@param lop binary operator that will be applied locally per worker

@param gop binary operator that will be applied globally among worker

@param part partitioning algorithm to schedule parallel iterations

@return a tf::Task handle

The task spawns asynchronous tasks to perform parallel reduction over a range with @c init.

The reduced result is store in @c init.

Unlike the iterator-based reduction,

index range-based reduction is particularly useful for applications that benefit from SIMD optimizations

or other range-based processing strategies.

@par One-dimensional range (`N` == 1)

@code{.cpp}

const size_t N = 1000000;

std::vector<int> data(N); // uninitialized data vector

int res = 1; // res will participate in the reduction

taskflow.reduce_by_index(

tf::IndexRange<size_t>(0, N, 1),

// final result

res,

// local reducer

[&](tf::IndexRange<size_t> subrange, std::optional<int> running_total) -> int {

int residual = running_total ? *running_total : 0.0;

for(size_t i=subrange.begin(); i<subrange.end(); i+=subrange.step_size()) {

data[i] = 1.0;

residual += data[i];

}

printf("partial sum = %lf\n", residual);

return residual;

// global reducer

std::plus<int>()

);

executor.run(taskflow).wait();

assert(res = N + 1);

@endcode

@par Multi-dimensional ranges (`N` > 1)

For @c N > 1, @c lop is invoked once per sub-box of the partitioned

Cartesian product, exactly like the @c callable passed to

tf::FlowBuilder::for_each_by_index. Each dimension of a tf::IndexRanges is

a <tt>std::tuple<T, T, T></tt> of (begin, end, step) accessible through

@c dim(d), so @c lop typically destructures it via structured bindings:

@code{.cpp}

// 2D range: rows x cols

tf::IndexRanges<int, 2> range(

tf::IndexRange<int>(0, rows, 1),

tf::IndexRange<int>(0, cols, 1)

);

double res = 0.0;

taskflow.reduce_by_index(

range,

res,

// local reducer

[&](const tf::IndexRanges<int, 2>& sub, std::optional<double> running_total) -> double {

double residual = running_total ? *running_total : 0.0;

auto [r0, r1, rs] = sub.dim(0);

auto [c0, c1, cs] = sub.dim(1);

for(auto r = r0; r < r1; r += rs) {

for(auto c = c0; c < c1; c += cs) {

residual += data[r][c];

}

return residual;

std::plus<double>()

);

executor.run(taskflow).wait();

@endcode

Range can be made stateful by using std::reference_wrapper.

@note

Please refer to @ref ParallelReduction for details.

template <IndexRangesLike R, typename T, typename L, typename G, PartitionerLike P = DefaultPartitioner>

Task reduce_by_index(R range, T& init, L lop, G gop, P part = P());

// ------------------------------------------------------------------------

// transform and reduction

// ------------------------------------------------------------------------

/**

@brief constructs an STL-styled parallel transform-reduce task

@tparam B beginning iterator type (satisfying tf::InputIteratorLike)

@tparam E ending iterator type (satisfying tf::InputIteratorLike)

@tparam T result type

@tparam BOP binary reducer type

@tparam UOP unary transformation type

@tparam P type satisfying tf::PartitionerLike

@param first iterator to the beginning (inclusive)

@param last iterator to the end (exclusive)

@param init initial value of the reduction and the storage for the reduced result

@param bop binary operator that will be applied in unspecified order to the results of @c uop

@param uop unary operator that will be applied to transform each element in the range to the result type

@param part partitioning algorithm to schedule parallel iterations

@return a tf::Task handle

The task spawns asynchronous tasks to perform parallel reduction over @c init and

the transformed elements in the range <tt>[first, last)</tt>.

The reduced result is store in @c init.

This method is equivalent to the parallel execution of the following loop:

@code{.cpp}

for(auto itr=first; itr!=last; itr++) {

init = bop(init, uop(*itr));

}

@endcode

Iterators can be made stateful by using std::reference_wrapper

@note

Please refer to @ref ParallelReduction for details.

template <InputIteratorLike B, InputIteratorLike E, typename T, typename BOP, typename UOP,

PartitionerLike P = DefaultPartitioner>

Task transform_reduce(B first, E last, T& init, BOP bop, UOP uop, P part = P());

/**

@brief constructs an STL-styled parallel transform-reduce task

@tparam B1 first beginning iterator type (satisfying tf::InputIteratorLike)

@tparam E1 first ending iterator type (satisfying tf::InputIteratorLike)

@tparam B2 second beginning iterator type (satisfying tf::InputIteratorLike)

View remainder of file in raw view

taskflow/taskflow/core/flow_builder.hpp at master · taskflow/taskflow · GitHub

Uh oh!

Expand file tree

Breadcrumbs

flow_builder.hpp

Latest commit

History

Breadcrumbs

flow_builder.hpp

File metadata and controls