D5.11: Refactor and Optimise the existing combinatorics Sage code using the new developed Pythran and Cython features.

[minrk]

• WP5: High Performance Mathematical Computing
• Lead Institution: CNRS
• Due: 2018-08-31 (month 36)
• Nature: Demonstrator
• Task: T5.6 (T5.6: HPC infrastructure for combinatorics #104)
• Proposal: p.51
• Final report (sources)

Computer experimentations in discrete mathematics, in particular enumerative and algebraic combinatorics, require high performance computing. The search spaces are often huge and the best algorithmic strategy for the exploration or problem spaces is not evident and often depend on
the answer to the question being probed. Let us cite the following description from~Maier et al. (Europar 2014):

Some discrete mathematical problems are embarrassingly parallel, and this
has been exploited for years even at Internet scale, \emph{e.g.} the “Great
Internet Mersenne Prime Search”. Many parallel algebraic computations
exhibit high degrees of irregularity, at multiple levels, with numbers and
sizes of tasks varying enormously (up to 5 orders of magnitude). They tend
to use complex user-defined data structures, exhibit highly dynamic memory
usage and complex control flow, often exploiting recursion. They make
little, if any, use of floating-point operations. This combination of
characteristics means that symbolic computations are not well suited to
conventional HPC paradigms with their emphasis on iteration over floating
point arrays.

This deliverable is about experimentations in combinatorics that involve low-level optimization and parallelization, as well as the integration of these techniques in the computer algebra system Sage.

[bpilorget]

#121 was merged into this deliverable after 3rd amendment to the contract

[nthiery]

@videlec, @hivert, @ClementPernet : where do we stand with this deliverable?

[nthiery]

This deliverable is the culminating point of T5.6: HPC infrastructure for Combinatorics (M1-M36)
It follows up D5.1 (#107): Turn the Python prototypes for tree exploration into production code, integrate to Sage, and subsumes D5.8 (#121): Explore the possibility to interface smoothly Pythran , Cython and Cilk++ which was merged into it.

Therefore the report would naturally give an overview of ODK's work in the area of high performance combinatorics, with two main directions:

• Refactoring and optimizing Sage's combinatorics code
• Exploring various technologies for high performance computations in combinatorics (e.g. Pythran, cppyy, Cilk, Spark, SIMD CPU instructions, GPU)

@hivert will take the lead for the latter part of the report.

@videlec: please confirm that you take the lead for the former part.

[nthiery]

I created a stub report: https://github.com/OpenDreamKit/OpenDreamKit/blob/master/WP5/D5.11/report.tex

There just remains to fill it in :-)

[ClementPernet]

@hivert :: could you feed me with some status update on this task. Even if the delivery is scheduled for next year, we need to write a status update in D1.5 (issue #21 ) of this fall's report. This is urgent (we need to write this update by thursday Aug. 30th).
Best would be if you could edit the report of D1.5 with these updates.

[videlec]

@nthiery thanks Nicolas. I will complete the report for "Refactoring and optimizing Sage's combinatorics code" (which is essentially Cython related). I can take the lead. Sorry for not responding before, I am at a conference.

[nthiery]

I will complete the report for "Refactoring and optimizing Sage's combinatorics code" (which is essentially Cython related). I can take the lead.

Perfect. Thanks Vincent.

[serge-sans-paille]

@ClementPernet is it ok if I make a short review of the master version of this deliverable today?

[ClementPernet]

@serge-sans-paille : thanks for proposing this. Sure please do. @videlec is also editing a part of the deliverable in the mean time, so maybe first focus on the other parts or try to synch with him to review it afterwards.

[hivert]

@videlec: Thanks for polishing what I wrote on the report. I wasn't meant to be finished and I planned to edit it more this afternoon but lot's of it is already done by you. I have more to add on the outreach of the work (invitation to seminar, my HPCombi code starting to be used by lib-semgroup itself used both by gap and Sage). To avoid conflict, cas you call me on the phone at my office (01601956599) to synchronize ?

[embray]

@hivert Let me know if you would like me to do any proofreading as well. I would go ahead and do it now but from the sound of it I should probably wait until a bit more editing is done.

[videlec]

@hivert sorry for the large rewrite of your part. I tried to simplify a lot the introductory part.

My time zone is GMT-4 (so now is early morning). I will not work on the report before 16:30pm (Paris time). Feel free to do any edit in the mean time.

I also have some edits to do regarding Cythonization in Sage.

[hivert]

@videlec : is wasn't meant that much as an introductory... Anyway thanks for the work !

[videlec]

@hivert: not everything you wrote is an introduction! Feel free to revert as much as you want if it does not fit. And remember that it is not a scientific report. Emphasis has to be put on results. The "rules" in the mail of Nicolas are of good help

• Context setting
  • what is the problem that is being addressed?
  • Why should we care about the deliverable?
  • what is the thing that has been created?
• Have an executive summary on the first page (just half a page).
  • why does this deliverable exist? (context)
  • have you achieved everything you set out to do?
  • what would be / are the next steps?
• Stating the obvious: for example if people (outside the project) are excited about it
• Provide introduction to topics, even for people not too familiar with the field
• Comment on other good (software) practices you may use without thinking about it (version control, testing, continuous integration, distribution)
• Comment on the testing that has been done, even if not automatic. If there is a prototype / demonstrator, explain it in more detail.
• Work relating to sustainability, should be mentioned, even if implicit (for example growing a community through workshops will help to make the project more sustainable).
• Anything with impact should be mentioned

[ClementPernet]

@hivert : could you edit a short paragraph summarizing the status of this deliverable in the report of D1.5
OpenDreamKit/WP1/D1.5/WP5.tex
https://github.com/OpenDreamKit/OpenDreamKit/blob/master/WP1/D1.5/WP5.tex#L170
or simply post a paragraph here which I could copy/past.
Thanks.

[hivert]

@ClementPernet: I'm not the best one to do that because most of my work was actually done on D5.8 which was merged with this one. I'd rather wait for @videlec input.

[hivert]

@videlec: I'm mostly done with writing my part (I still need some rereading). However due to the big git problem I've pushed to a new branch namely https://github.com/OpenDreamKit/OpenDreamKit/tree/D5.11 Please pull, complete at will. Since the title of the deliverable concern more your part than mine, I leave it to you to write the introduction and the conclusion. Please ask for some input if needed.

[videlec]

@hivert: thanks. looking at it now.

[videlec]

@hivert cilk++ is officially deprecated by Intel in favor of TBB. Though there is the Cilk Hub initiative: http://cilk.mit.edu/. Do you want to add a word about this?

[hivert]

I might a a word but it's the first time I'm hearing about it. It seems quite new.

[videlec]

It is now very late for me. I am basically done. I will reread to provide better phrasing. Any proofreading welcome at this stage.

[serge-sans-paille]

Just pushed a small review of the spelling / phrasing.

[hivert]

@ClementPernet I've just contributed a small page to the overall WP5 report describing the result for HPC-combi. Please reread and comment.

[embray]

@hiver @nthiery I have pushed my edits to the report.

[embray]

Hold on...merge conflicts...wtf

[embray]

Ok fixed!

[hivert]

Thanks to @serge-sans-paille and @embray for the rereading.

[hivert]

@videlec: Unless you have something more to to, this deliverable is ready to go !!! Can you confirm that its Ok for you ?

[videlec]

@hivert I am ok. Are you doing the submission?

[hivert]

@videlec : no ! That's the role of the big boss ! I'm telling him we are ready.

[ClementPernet]

@hivert : I checked your report on the WP5 section of D1.5. Looks good to me. I just see that D5.1 is still being mentionned although it has already been delivered. I assume this is to put the remaning things in context. Maybe you could state it more clearly.

[nthiery]

Report submitted; thanks @hivert and @videlec for the sprint :-)
I am looking forward more refactoring in the combinatorics code!

[nthiery]

Please edit the first entry of this issue to look like, e.g., that of #64, including in particular a copy of the introduction.

[nthiery]

I am also looking forward the dissemination of all the insight in this report, e.g. in the form of a blog post, or maybe a paper some day?

[hivert]

@ClementPernet : Is WP5 now better ?

[ClementPernet]

@hivert : yes. Everything is now fine with me on the WP5 part of D1.5

[nthiery]

For the record, this deliverable was approved on March 14th of 2019. Closing!
Thanks everyone :-)

[nthiery]

Suggestion: please prepare a demo in notebook format; see #289.