deepsea-inria/encore

A C++ library for writing fine-grain parallel programs

encore's Issues

Find and fix a space leak somewhere in encore

valgrind mixed.dbg -lgn 4 -dag_freq 2
==78864== Memcheck, a memory error detector
==78864== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==78864== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==78864== Command: mixed.dbg -lgn 4 -dag_freq 2
==78864==
nb_promotions 52
nb_steals 0
exectime 0.360
==78864==
==78864== HEAP SUMMARY:
==78864== in use at exit: 183,296 bytes in 28 blocks
==78864== total heap usage: 1,898 allocs, 1,870 frees, 2,868,384 bytes allocated
==78864==
==78864== LEAK SUMMARY:
==78864== definitely lost: 110,592 bytes in 27 blocks
==78864== indirectly lost: 0 bytes in 0 blocks
==78864== possibly lost: 0 bytes in 0 blocks
==78864== still reachable: 72,704 bytes in 1 blocks
==78864== suppressed: 0 bytes in 0 blocks
==78864== Rerun with --leak-check=full to see details of leaked memory
==78864==
==78864== For counts of detected and suppressed errors, rerun with: -v
==78864== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Parallelize loop over neighbor list in PDFS example

Find a good semantics for async/finish (aka join_plus/spawn_minus)

The problem currently is that the join_plus block does not interact properly with, say, parallel_for. In pdfs, for example, the parallel_for on the neighbor loop is bogus because the loop splits do not get counted appropriately by the join counter of the enclosing join_plus block.

Introduce unit test and benchmarking pbench scripts

Use pbbs-include repository to access PBBS header files

All benchmarking harnesses should live in the cpp files in the bench/edsl folder.

Sequential codes in sequence.cpp are now redundant and should be replaced by the functions in the PBBS header files.

Enhance makefile

It should at least track dependencies of header files. Maybe better is to use an alternative build system.

Consider benchmarking the scan function in scan.cpp

This task is to be considered only if the PBBS library scan is much faster than encore's scan and we need to understand why.

Introduce synchronized printing routines and clean system teardown for error conditions

Write a pbench script to prepare benchmarking PBBS

Introduce new stats per Arthur's suggestion

Stats to report:

• Work by nb basic blocks.
• span

Introduce new macros to simplify declaration of parallel loops

Before:

static constexpr int nb_loops = 1;
encore_private_activation_record_begin(encore::edsl, maxIndex, nb_loops)
int s; int e;
encore_private_activation_record_end(encore::edsl, maxIndex, sar, par, dc, get_dc)

After:

encore_private_activation_record_begin(encore::edsl, maxIndex)
encore_parallel_for_declare()
int s; int e;
encore_private_activation_record_end(encore::edsl, maxIndex, sar, par, dc, get_dc)

In other words, declare each loop inline by a macro call, such as encore_parallel_for_declare(), encore_parallel_combine_declare(), etc.

Extend lazy loop splitting in order to implement our parallel BFS

This encoding should show a clear advantage for our technique compared to, say, LS BFS or to PBBS BFS.

Clean up macro names in edsl

Add support for hwloc and numa interleaving by default

Investigate using some lightweight machine learning a la Oracular Scheduling to tune inner loops

Consider introducing a debugging facility whereby the scheduler randomizes the schedule

The idea is to randomize the ordering of the frontier so that one can simulate concurrency.

Introduce leaf-level looping constructs

The purpose is to properly encode serial and parallel loops in encore. The idea is that encore realizes efficient looping in general by properly controlling grain size. The input format of the new looping operators should be such that each loop body of a leaf level loop (i.e., innermost loop) is expressed by a lambda function and the lambda function is parameterized by a range (i.e., lo, hi).

Add logging support, and in particular support to generate utilization plots

Double check the logic in the cactus stack module

Ask Filip or Adrien to help.

Write the proper scan algorithm, using encore sequential loops instead of calls to c functions

Do this step after generalizing the parallel loop facilities.

Introduce a cmdline option to disable encore diagnostics printing

Idea:

--disable_diagnostics_reporting

Better:

-diagnostics_reporting stdout | stderr | ...

Use guarded pages to reduce memory use of native threads

https://github.com/brianwatling/libfiber/blob/master/src/fiber_context.c

Reintroduce callbacks to help manage initialization

In particular, make sure that sequence::initialize() is always called by using a callback to get encore's own initialization to call sequence::initialize().

Implement a benchmark to evaluate performance of nested parallel loops

Two good targets:

• sparse matrix by dense vector multiplication; tests ability to handle imbalance
• dense matrix by dense vector multiplication; tests ability to handle regular workload

Find better names for operators spawn_minus, spawn_plus, etc.

Fix bug causing the split method of frontier to fail asserts

The bug seems to be related to lazy splitting of parallel loops.

See if the conditional branch instruction can be improved by removing indirection on branches

It should be doable, given that the indirection array is never really used.

Generalize lazy binary splitting facility to handle more general patterns than just parallel_for

We want to handle:

• parallel_for loops (there is no combining operator; all parallel iterations produce data for one common consumer vertex)
• reductions
  • need proper support for constant and non constant time combining operators
  • maybe provide special support for combining operators that are both associative and commutative; one application is parallel bfs, where we have a reduction that is constructing a bag in a divide and conquer fashion; the operation that merges two given bags is a commutative operation
• speculative_for loops?

Consider whether it's possible to introduce a new native mode based on new LLVM calling conventions

New LLVM calling conventions were implemented by Manticore team. Ask them what it's all about.

Enable and test scalable incounter and outset structures

Also, remember to test parallel walk of outset structure.