On Thu, Nov 19, 2015 at 1:13 PM, Oswin Krause < Oswin.Krause@ruhr-uni-bochum.de> wrote:

Hi,

This sounds like a specific solution to a general need for schedulers.

...

This proposal can work on top of any scheduler that allows for dependency graphs. You could see this library as a specific application of scheduling linear algebra tasks, because we know exactly how the dependencies are and how to order stuff. Therefore, we can completely hide the scheduling.

Have you looked at the current proposals from the various sg groups

...

such as sg1? Do they not help to solve your problem? Now is the time to speak up if they don't. Go find Michael Wong or Hans Boehm.

I am not sure about the current state of the proposals, I only remember a recent discussion about executors where I raised concerns about possible deadlocks and missing guarantees. Anyways, I would not know where to start looking for the current state of the proposals.

The C++ committee's papers are a good place to start. See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/ Work from newest (at the end) to oldest (at the top). You might be particularly interested in: P0159R0 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0159r0.html Draft of Technical Specification for C++ Extensions for Concurrency, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0159r0.html N4514 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4514.pdf Technical Specification for C++ Extensions for Transactional Memory, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4514.pdf N4507 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4507.pdf Technical Specification for C++ Extensions for Parallelism , http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4507.pdf http://lists.boost.org/mailman/listinfo.cgi/boost --Beman

On 21/11/2015 06:12, Sebastian Schaetz wrote:

asynchrony and optimization of the AST are very interesting techniques that the DL community should leverage. There is a lot of existing knowledge and code in this area so in addition to looking at standard proposals I would recommend you look into advanced expression template libraries like NT2 [0] or Eigen [1] when researching previous work. I would also recommend you look into HPX [2].

FYI, we have experimental support of HPX inside NT2 already. My PHD student defended on that recently. Need to merge that to NT2 master stll.

On 2015-11-21 06:12, Sebastian Schaetz wrote:

...

Hi Oswin,

On Thursday, November 19, 2015 at 9:56:13 AM UTC-5, Oswin Krause wrote:

...

I would like to propose a new library to boost: asynchronous blas.

asynchrony and optimization of the AST are very interesting techniques that the DL community should leverage. There is a lot of existing knowledge and code in this area so in addition to looking at standard proposals I would recommend you look into advanced expression template libraries like NT2 [0] or Eigen [1] when researching previous work. I would also recommend you look into HPX [2].

Hi Sebastian (and others),

I am a bit confused by the replies. Is this a "yes, there is interest but do some proper research beforehand"?

Of course I do know Eigen, Armadillo and NT2 as I had to do some research in the past for the linked library. For the CPU part i was indeed planning a system with an interface similar to HPX,but I can not rely on HPX because It would then be a mandatory external library - and distributed computations are currently not in the scope of the project(honestly, I do not have enough experience with distributed computing to start such an endeavor).

<rant> Why do people fall into the trap of the NIH syndrome over and over again? *sigh* </rant> Anyways, while HPX supports distributed computing, you don't have to use it for this. HPX can be used just fine for SMP style (local only) applications as well. In fact we have shown that by simply switching from std::async/std::future to hpx::async/hpx::future you can achieve a speedup of up to a factor of 3-4 (depending on the application). That does not entail utilizing some of the more sophisticated features HPX provides you with (extending futures like proposed by the Concurrency TS, dataflow, parallel algorithms, task regions, GPU integration, etc.). Those usually give you an additional benefit in terms of speedup, readability, and maintainability. Regards Hartmut --------------- http://boost-spirit.com http://stellar.cct.lsu.edu

Robert,

...

<rant> Why do people fall into the trap of the NIH syndrome over and over again? *sigh* </rant>

Hmmmm - Is HPX a boost library? Maybe you want to affiliate HPX with boost in the manner that spirit is. Might make for an interesting review discussion.

HPX is actually at least 5 (if not more) different libraries, so this would fall through even before any discussion has started. It is also ~250k LOC, nobody would want to review that anyways. While I understand the significance of being part of Boost (in terms of legal and company BS), I don't think that it would be worth the effort at this point for us to invest time into such an endeavor. That said - if somebody would be interested in turning HPX (or part of it) into his 'own' Boost library - please be our guest. We would be in full support for such an effort. We (HPX) have always used Boost as our role model for code quality, portability requirements, coding guidelines, license, review discipline (I believe we're even further along the road here if compared to Boost), etc. Thus - if somebody is interested in code quality and excellent support - I don't see any reason not to use HPX in the first place, even if it's external. It wouldn't be more 'external' than using Boost. Regards Hartmut --------------- http://boost-spirit.com http://stellar.cct.lsu.edu

...

Anyways, while HPX supports distributed computing, you don't have to use it for this. HPX can be used just fine for SMP style (local only) applications as well. In fact we have shown that by simply switching from std::async/std::future to hpx::async/hpx::future you can achieve a speedup of up to a factor of 3-4 (depending on the application).

This for example would be a reason for me to provide a default implementation using std::future that i can exchange by the hpx:: versions using a preprocessor directive.

Btw: is there a specific reason for that speedup? is there just less overhead of the implementation or is it improved scheduling of tasks?

It's mainly because of a) very efficient user level threading, and b) low overhead synchronization primitives. Regards Hartmut --------------- http://boost-spirit.com http://stellar.cct.lsu.edu

Hi, giving a small heads-up. There is now a minimal PoC at https://github.com/Ulfgard/aBLAS . Minimal in the sense that i took my existing LinAlg, ripped it apart and rewrote it partially to fit the new needs of the library. Only cpu is implemented, yet. I am open for suggestions, helpful advice and of course people who are interested to work on it. I am not too happy with the scheduling interface right now and its implementation looks a bit slower than necessary, but i think this will evolve over time. two basic examples showing what the library already can do are given in examples/ . For ublas users this should not look too foreign. For all who are interested, here is the basic design and the locations in include/aBLAS/: 1. computational kernels are implemented in kernels/ and represent typical bindings to the BLAS1-3 functionality as well as a default implementation (currently only dot,gemv,gemm and assignment are tested and working, no explicit bindings included, yet). kernels are enqueued in the scheduler via the expression template mechanisms and kernels are not allowed to enqueue kernels recursively. 2. a simple PoC scheduler is implemented in scheduling/scheduling.hpp. It implements a dependency graph between work packages and work is enqueued into a boost::thread::basic_thread_pool when all its dependencies are resolved. A kernel is enqueued together with a set of dependency_node objects which encapsulate dependencies of variables the kernel uses (i.e. every variable keeps track about what its latest dependencies are and whether these dependencies read from it or write to it). The current interface should be abstracted enough to allow implementation using different technologies(e.g. it should be possible to implement the scheduler in terms of HPX.). One of the tasks of the scheduler is to allow creation of closures where variables are guaranteed to exist until all kernels using them are finished as well as moving a variable into a closure. This is used to prevent an issue similar to the blocking destructor of std::future<T>. Instead of blocking, the variable is moved into the scheduler which then ensures lifetime, until all kernels are finished. This of course requires the kernels to be called in a way that they can cope with the moving of types. what is currently missing is "user created dependencies" to be used in conjunction with the gpu (as gpus are fully asynchronous, we have to register a callback that notifies the scheduler when the gpu is done with its computations just as the worker threads do). 3. basic matrix/vector classes are implemented in matrix.hpp and vector.hpp. The implementation is a bit convoluted for the "move into closure" to work. Basically they introduce another indirection. When a kernel is created, it references a special closure type of the variable (vector<T>::closure_type), which references that indirection. 4. the remaining files in include/aBLAS*.hpp implement the expression templates, which are similar to uBLAS. There are two types distinguished using the CRTP classes matrix_expression and vector_expression. Type is the exact type of the expression, Device marks the Device this is working on (cpu_tag or gpu_tag). The second template parameter ensures that one can not mix gpu and cpu expresions unless the operation explicitly allows this. While this looks clumsy, it removes code duplication between the different device types as most of the code can be used for both implementations. assignment.hpp implements the basic assignment operators (Except op=). A += B either calls kernel::assign<>(A,B) if B can be evaluated efficiently elementwise (e.g. A+= 2*A1+A2-A3) or calls B.plus_assign_to(A) which then assigns the terms one-by-one using their specialized kernels (e.g. A+=prod(B,C)+D is evaluated as kernels::gemm(B,C,A); kernels::assign<...>(A,D);) matrix/vector_proxy.hpp implement subranges, rows-of-matrix-operations, etc and matrix/vector_expression the algebraic operations. Best, Oswin

On 11/22/15 6:06 AM, Oswin Krause wrote:

On 2015-11-21 06:12, Sebastian Schaetz wrote:

Of course I do know Eigen, Armadillo and NT2 ... but I can not rely on HPX because It would then be a mandatory external library -

The question for me is: is there enough interest in such a thing that it is worthwhile for me to create a minimal prototype on which a discussion could be based on?

Hmmm - if you made a boost library which implemented what you desire, wouldn't that become an "external library" which you could not then use? Is the whole motivation of this proposal to work around some internal prohibition of "external code" imposed for some non-technical reasons like legal department BS or grant requirements or ??? I'm not getting the motivation here. Robert Ramey

Hi David,

And your work would be recognized as being part of ublas directly and be used right away by thousands of users. Let me know if you're interested contributing back to ublas instead.

Yes, I am interested, but currently I do not see a roadmap as ublas is SO big, that I fear that I can not fix as much code as my proposed changes would break (even without the asynchronous part, gpus...). One of the starting points of my rewrite was that I deleted around 40k lines of ublas code before i started and then designed the interface around a defined subset of features (namely one dense format and one sparse format, later adding the triangular packed format. I still haven't gotten sparse right, though.). From then on i decided to break the functionality apart in a few places (assignment, kernels, and iterators) and use the expression templates as a simple connection between the parts. Another point: I would not propose a major change to an existing boost library without triggering a formal boost review process - this change would break any code that relies on any ublas internals. Best, Oswin

Cheers, David

On Thu, Nov 19, 2015 at 2:55 PM, Oswin Krause < Oswin.Krause@ruhr-uni-bochum.de> wrote:

...

Hi list,

Disclaimer: What I am proposing here does not exist (yet). But it will in the near future and if there is interest i would like to give something back to the boost community.

I would like to propose a new library to boost: asynchronous blas.

What is it and what can I do with it? It is a linear algebra library where all computations are carried out in an asynchronous manner on GPU and CPU. Computing a matrix-matrix product does not block the current thread but instead launches a task which at some point returns with a result, allowing the main thread to continue until the result is needed. GPU and CPU tasks can be started at the same time depending on each other (e.g. a CPU computation waits until the GPU returned some needed result and vice-versa)

Why is this important? Which problems does it solve? Many linear algebra libraries are target towards either a) solving a few large linear algebra problems b) solving many small similar problems

This library is targeted towards the middle ground: a medium amount of decently sized problems. Here the problem is that it is often hard to use all the computing resources available as a single problem will not exhaust the device resources and there is no easy way to launch several similar tasks in parallel. This problem occurs often in GPU computing where out-of-order execution of kernels is used to fill up the device. Similarly, it is often hard to make CPU and GPU work together as GPU tasks are asynchronous while CPU tasks are often synchronous and it is not straight forward to couple both without blocking either CPU or GPU.

How does it work? Expression templates similar to boost::ublas are used to create a dependency graph: which object is used in which computations and which tasks have to wait to ensure a correct outcome?

a simple case would be two independent computations like

matrix A=prod(B,trans(B)); matrix C=prod(trans(B),B);

a normal library like ublas would wait until A is computed before C is evaluated. Instead, it can be more efficient to just add the two tasks to a list and let worker threads execute them as soon as resources are available. First the computation of A is put into the graph and A is marked as "being written to" while B is marked as "being read". When C is added to the list, it does not depend on the first computation as several tasks can read from B at the same time. So another worker thread can grab the task and execute it.

If we now add the task

B += prod(D,prod(C,trans(D));

the library computes it as

matrix temp = prod(C,trans(D); B += prod(D,temp).

temp can be computed as soon as C is computed. But B can only be computed after A and temp are computed as we can only write to B after all previous tasks using B are finished.

Are you qualified? I am main contributor to https://github.com/Shark-ML/Shark/ and as part of it I forked ublas https://github.com/Shark-ML/Shark/tree/master/include/shark/LinAlg/BLAS which now uses several linear algebra libraries as possible backends (ATLAS, openBLAS...).

What is the timeline? I would start developing a minimal example ASAP based on the rewrite of ublas above. I would use a minimum set of features (only dense square matrices) and basic GPU support.

Opinions?

Best, Oswin

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost