Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

P1673 A free function linear algebra interface based on the BLAS #557

Open
wg21bot opened this issue Jun 28, 2019 · 14 comments
Open

P1673 A free function linear algebra interface based on the BLAS #557

wg21bot opened this issue Jun 28, 2019 · 14 comments

Comments

@wg21bot
Copy link
Collaborator

@wg21bot wg21bot commented Jun 28, 2019

P1673R0 A free function linear algebra interface based on the BLAS (Mark Hoemmen, Daisy Hollman, Christian Trott, Daniel Sunderland, Nevin Liber, Siva Rajamanickam, Li-Ta Lo, Graham Lopez, Peter Caday, Sarah Knepper, Piotr Luszczek, Timothy Costa)

@tituswinters
Copy link
Collaborator

@tituswinters tituswinters commented Jul 8, 2019

This R0 needs to be forwarded by some/all of the relevant SGs before going to LEWG for design review. Removing the LEWG label.

@brycelelbach
Copy link
Collaborator

@brycelelbach brycelelbach commented Jul 12, 2019

Mark, if you want some early design review, we can look at this in LEWGI.

@brycelelbach
Copy link
Collaborator

@brycelelbach brycelelbach commented Jul 16, 2019

Cologne 2019-07 LEWGI Minutes

P1673R0 & P1674R0 C++ BLAS Library: Design Feedback

Champion: Christian Trott

Minute Taker: Tobias Loew

Start Overview: 07-16 8:52

Start Review: 9:20

Algorithms are parameterized on a concept, iterators. The proposed linear algebra algorithms are parameterized on a concrete view type, mdspan.

Do people need to spell scaled_scalar? Can it just be an implementation-defined type with certain properties.

SG1 needs to review this from a parallelization/vectorization angle.

How should we handle outputs in the API?

Explore a range-style lazy view API.

End: 10:17

CONSENSUS: Bring a revision of P1673R0, exploring conceptification of mdspan and a range-style lazy API, to LEWGI for further design feedback.

@jensmaurer jensmaurer removed this from the 2019-07 milestone Aug 23, 2019
@wg21bot
Copy link
Collaborator Author

@wg21bot wg21bot commented Oct 15, 2019

P1673R1 A free function linear algebra interface based on the BLAS (Mark Hoemmen, Daisy Hollman, Christian Trott, Daniel Sunderland, Nevin Liber, Siva Rajamanickam, Li-Ta Lo, Graham Lopez, Peter Caday, Sarah Knepper, Piotr Luszczek, Timothy Costa)

@wg21bot wg21bot added this to the 2019-11 milestone Oct 15, 2019
@brycelelbach
Copy link
Collaborator

@brycelelbach brycelelbach commented Nov 5, 2019

Note that the LEWGI feedback from Cologne didn't make it clear that SG1 needs to see this, but they certainly do. Sorry, my mistake.

@brycelelbach
Copy link
Collaborator

@brycelelbach brycelelbach commented Nov 5, 2019

This was forwarded to LEWG by SG14 at Cologne.

@brycelelbach
Copy link
Collaborator

@brycelelbach brycelelbach commented Nov 6, 2019

Belfast 2019-11 LEWGI Minutes

P1673R1 Free Function Linear Algebra Library

Champion: Mark Hoemmen

Minute Taker: Andreas Weis

Start Review: 11-05 8:55

Are the algorithms inplace (like sort) or non-modifying (like transform)?

Should dimensional errors be checked? If we know them all at compile time, we should check them.

Make these constexpr? May not be possible/easy in version 1 - constexprification is ongoing, and you may have dependencies on that.

Walking through the matrix multiply code example was very useful.

Add more examples showing the use of the views.

Do we need to have the mdarray overloads in version 1?

Start Polling: 10:12

POLL: We are comfortable with the design of "mdspan transformations" in P1673 (scaled_view, transpose_view, etc).

Strongly For Weakly For Neutral Weakly Against Strongly Against
0 11 0 0 1

Attendance: 16

That's got consensus.

POLL: Dimensional errors should be checked at compile time (e.g. Mandates clauses) if all dimensions are known at compile time; otherwise, they should be preconditions (e.g. Expects clauses).

NO OBJECTION TO UNANIMOUS CONSENT

Attendance: 16

POLL: Making the linear algebra algorithms in P1673 constexpr should be a priority for the initial release.

Strongly For Weakly For Neutral Weakly Against Strongly Against
1 2 7 3 0

Attendance: 16

No consensus.

POLL: mdarray overloads should be a priority for the initial release.

Strongly For Weakly For Neutral Weakly Against Strongly Against
1 1 4 3 1

Attendance: 17

Weak consensus against.

POLL: Conceptifying input and output arguments should be a priority for the initial release.

Strongly For Weakly For Neutral Weakly Against Strongly Against
1 2 3 3 1

Attendance: 16

No consensus.

Break: 10:22

Resume: 10:44

Start Polling: 11:15

POLL: Packed layouts are a priority for the initial release.

Strongly For Weakly For Neutral Weakly Against Strongly Against
3 6 4 0 1

Attendance: 18

SA: I want to start with something as simple as possible.

That has consensus.

POLL: We are comfortable with the design of layout_blas_general and layout_blas_packed in P1673.

NO OBJECTION TO UNANIMOUS CONSENT

Attendance: 18

POLL: Linear algebra algorithms that produce a single scalar output should return the output.

Strongly For Weakly For Neutral Weakly Against Strongly Against
2 8 2 1 2

Attendance: 18

That has consensus.

POLL: The intermediate type used for reduction-style linear algebra algorithms should be the type of the initial value, or the element type derived from the inputs if there is no initial value (e.g. what std::reduce/std::accumulate does).

Strongly For Weakly For Neutral Weakly Against Strongly Against
2 7 3 1 0

Attendance: 18

That has consensus.

A: I want an explicit template parameter.

POLL: Send P1673 (Free Function Linear Algebra Library) to LEWG and SG1.

Strongly For Weakly For Neutral Weakly Against Strongly Against
12 1 3 0 0

Attendance: 18

That has consensus.

After speaking with the SG1 chair, SG1 doesn't need to see this.

End: 11:31

CONSENSUS: LEWGI sends P1673R1 (Free Function Linear Algebra Library), with the guidance below, to LEWG.

  • Add the walkthrough of the matrix multiply code to the presentation.
  • Add more examples showing the use of mdspan transformations.
  • Rename "mdspan views" in the paper to something else (such as "mdspan transformations").
  • Propose batched linear algebra in a separate paper, not this one.
  • Remove mdarray overloads.
  • Check dimensional errors at compile time (e.g. Mandates clauses) if all dimensions are known at compile time; otherwise, make them precondition violations (e.g. Expects clauses).
  • Make linear algebra algorithms that produce a single scalar output return that output.
  • Make the intermediate type used for reduction-style linear algebra algorithms the type of the initial value, or the element type derived from the inputs if there is no initial value (e.g. what std::reduce/std::accumulate does).

@jensmaurer jensmaurer removed this from the 2019-11 milestone Jan 3, 2020
@jensmaurer jensmaurer added this to the 2020-02 milestone Jan 3, 2020
@wg21bot
Copy link
Collaborator Author

@wg21bot wg21bot commented Jan 18, 2020

P1673R2 A free function linear algebra interface based on the BLAS (Mark Hoemmen, Daisy Hollman, Christian Trott, Daniel Sunderland, Nevin Liber, Siva Rajamanickam, Li-Ta Lo, Damien Lebrun-Grandie, Graham Lopez, Peter Caday, Sarah Knepper, Piotr Luszczek, Timothy Costa)

@brycelelbach brycelelbach added this to 2020-06-15 Telecon in Library Evolution Telecons May 10, 2020
@FabioFracassi
Copy link
Collaborator

@FabioFracassi FabioFracassi commented Jun 22, 2020

2020-06-15 Library Evolution Telecon

P1673R2: BLAS Linear Algebra

2021-06-15 Library Evolution Telecon Minutes

Chair: Fabio Fracassi

Champion: Christian Trott

Minute Taker: Guy Davidson, Ben Craig

POLL: We want to put arguments in math order (result first) as opposed to C++/BLAS order (result last).

Strongly Favor Weakly Favor Neutral Weakly Against Strongly Against
2 0 4 10 5

Attendance: 29

Outcome: consensus against, leave parameter order as proposed in the paper

POLL: We want the paper authors to investigate using existing C++20 concepts (e.g. move_constructible) to constrain the algorithms.

No objection to unanimous consent.

Attendance: 29

Outcome: consensus.

POLL: We want to require the paper authors to investigate that the requirements/concepts match with the conceptified numerics algorithms.

Strongly Favor Weakly Favor Neutral Weakly Against Strongly Against
1 12 5 2 1

Attendance: 29

Outcome: consensus

Chair Notes:

We did not take the following polls, but the topics were discussed at length, so it is likely that questions along those lines will come up again. The next revision of the paper should do its best to address these:

  • We want the paper authors to explore using a dedicated namespace for this library.
  • We want to reserve the name scale_view/transpose_view (of mdspan) (for use with ranges)
  • We want to make the interface compatible with transpose_view/scale_view compatible with ranges transpose view.
  • Support for GPU/different memory regions?

The naming discussion uncovered a general issue, when there are names that might fit into different contexts. A informational or policy paper exploring this design space would be welcome.

The general theme of the discussion was integration into the C++ Standard Library. The Paper introduces new (specialized) algorithms, so naturally there is a question on how well they integrate with currently existing algorithms (especially the algorithms in the numeric header). Another concern is proper conceptification.

@wg21bot
Copy link
Collaborator Author

@wg21bot wg21bot commented Apr 25, 2021

P1673R3 A free function linear algebra interface based on the BLAS (Mark Hoemmen, Daisy Hollman, Christian Trott,Daniel Sunderland, Nevin Liber ,Li-Ta Lo, Damien Lebrun-Grandie, Graham Lopez, Peter Caday, Sarah Knepper, Piotr Luszczek, Timothy Costa)

@brycelelbach
Copy link
Collaborator

@brycelelbach brycelelbach commented Jun 22, 2021

2021-06-22 Library Evolution Telecon

P1673R3: BLAS Linear Algebra

Slides

2021-06-22 Library Evolution Telecon Minutes

Chair: Bryce Adelstein Lelbach

Champion: Mark Hoemmen

Minute Taker: Ben Craig

Start: 2021-06-22 10:05 Pacific

Does this proposal have:

  • Examples?
    • Yes. They're at the end of the paper in an appendix; at least one should probably be moved up earlier.
  • Field experience?
    • Implementation experience?
    • Usage experience?
    • Deployment experience?
  • Performance considerations?
    • Yes.
  • Discussion of prior art?
    • Yes. This is based on the the BLAS.
  • Changes Library Evolution previously requested?
    • Yes. See slides and paper changelog.
  • Wording?
    • Yes. Reviewed by wordsmith Daniel Sunderland.
  • Feature test macro?

The authors explored conceptification in two areas, and they believe that
we should not pursue it for either area:

  • Element types (e.g. a number concept).
    • They believe conceptification similar to P1813 is likely too constraining. Numerical linear algebra deals with the world of the digital representation of numbers, not the mathematical concept of numbers. People care about non-associativity and non-commutativity.
  • mdspan (e.g. a multi-dimensional span concept).
    • They believe conceptification would likely require replicating much of the mdspan machinery and doesn't seem like it would have any real benefit.

Topics to Polls:

  • Which algorithms should be included in the first version of this?
  • Are the type constraints for the algorithms and how they are expressed correct?
  • Are we okay with not trying to constrain the element types with a number concept like those from P1813?

POLL: The linear algebra algorithms in P1673 do not need to be constrained on the mathematical concept of numbers.

Strongly Favor Weakly Favor Neutral Weakly Against Strongly Against
12 10 1 0 0

Attendance: 30

# of Authors: 5

Author Position: 5x SF

Outcome: Consensus in favor.

N: I want to see semantic requirements, not just syntactic requirements, and I don't see that today.

Investigate where (move) assignable / constructible requirements (etc) are missing.

POLL: The linear algebra algorithms in P1673 should only support integer types (including extended integer types), floating point types (including potential future extended floating point types), and complex types of the the preceding two categories.

Strongly Favor Weakly Favor Neutral Weakly Against Strongly Against
0 0 8 7 6

Attendance: 30

# of Authors: 5

Author Position: WAs and SAs.

Outcome: That has consensus against.

POLL: We are okay with the style of constraints used in the linear algebra algorithms in P1673R3, which are solely syntactic, aside from assignment and construction.

Strongly Favor Weakly Favor Neutral Weakly Against Strongly Against
4 15 2 1 0

Attendance: 30

# of Authors: 5

Author Position: WFs and SFs.

Outcome: That has consensus in favor.

WA: This says that there's not really any requirements. It's not clear what these algorithms do.

End: 11:39

Paper Feedback

Add a table of contents to paper.

Add a summary table of which algorithms are included and not included.

Make the examples more prominent in the paper. Move some of them earlier in the paper into the design section.

Slides Feedback

Publish slides as a P paper.

Add slide numbers.

Slide typo: "Open-source impl.s" on "Basic Linear Algebra Subprograms" slide.

Some of the fonts in the slides render oddly ("ExecutionPolicy", for example). Please embed the fonts.

Summary

We reviewed P1673, which proposes Standard C++ linear algebra algorithms inspired by the BLAS, a standard for linear algebra. We've seen this proposal a few times now, and the authors have been diligent in responding to the changes and explorations Library Evolution as requested.

One of those explorations consumed much of our time today. In our previous review, we had asked the authors to explore constraining the element types in linear algebra algorithms using number concepts similar to those in P1813.

The authors considered this, but they believe that this will be overly constraining; numeric linear algebra doesn't necessarily deal in the formal notion of numbers. Library Evolution had a preference to not use number concepts such as those from P1813.

We also discussed what exact requirements should be placed on element types in these algorithms, and subsequently what we can say about what these algorithms do. Two different options were identified:

  1. We could define the effect and results of the algorithms, and then describe the syntactic and semantic requirements that arise from that definition.
  2. We could say that the algorithms are equivalent to whatever happens when you apply a certain series of operations, and then describe the syntactic requirements that are implied by those operations.

Library Evolution had a preference for the second option, describing the the algorithms in terms of what operations they are equivalent to and constraining the element types based on what syntax is needed by those operations.

It was noted that some requirements are missing, in particular for assignability and constructibilty. The authors will address this in the next revision.

Outcome

Bring a revision of P1673R3 (BLAS Linear Algebra), with the guidance below, to Library Evolution for further design review.

  • Add a table of contents.
  • Make examples more prominent in the paper; at least some of them should appear early in the paper.
  • Add a table summarizing which BLAS routines are included as algorithms and which are omitted.
  • Audit all requirements and add any missing assignability and constructibility requirements.
  • Consider using exposition-only concepts and requires clauses to express requirements more clearly.

Publish the presentation slides for P1673R3 (Linear Algebra) as a P paper, with the guidance below.

  • Add slide numbers.
  • Fix "Open-source impl.s" typo on "Basic Linear Algebra Subprograms" slide.

@wg21bot
Copy link
Collaborator Author

@wg21bot wg21bot commented Aug 23, 2021

P1673R4 A free function linear algebra interface based on the BLAS (Mark Hoemmen, Daisy Hollman,Christian Trott,Daniel Sunderland,Nevin Liber,Alicia KlinvexLi-Ta Lo,Damien Lebrun-Grandie,Graham Lopez,Peter Caday,Sarah Knepper,Piotr Luszczek,Timothy Costa)

@wg21bot
Copy link
Collaborator Author

@wg21bot wg21bot commented Oct 26, 2021

P1673R5 A free function linear algebra interface based on the BLAS (Mark Hoemmen, Daisy Hollman,Christian Trott,Daniel Sunderland,Nevin Liber,Alicia KlinvexLi-Ta Lo,Damien Lebrun-Grandie,Graham Lopez,Peter Caday,Sarah Knepper,Piotr Luszczek,Timothy Costa)

@wg21bot
Copy link
Collaborator Author

@wg21bot wg21bot commented Dec 18, 2021

P1673R6 A free function linear algebra interface based on the BLAS (Mark Hoemmen, Daisy Hollman,Christian Trott,Daniel Sunderland,Nevin Liber,Alicia KlinvexLi-Ta Lo,Damien Lebrun-Grandie,Graham Lopez,Peter Caday,Sarah Knepper,Piotr Luszczek,Timothy Costa)

@jensmaurer jensmaurer removed this from the 2021-telecon milestone Jan 1, 2022
@jensmaurer jensmaurer added this to the 2022-telecon milestone Jan 1, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
6 participants
@brycelelbach @FabioFracassi @tituswinters @jensmaurer @wg21bot and others