hpx icon indicating copy to clipboard operation
hpx copied to clipboard

Adding local work requesting scheduler that is based on message passing internally

Open hkaiser opened this issue 2 years ago • 2 comments

This adds a new experimental work-requesting scheduler to the list of existing schedulers

  • Using uniform_int_distribution with proper bounds
  • Removing queue index from thread_queues as it was unused
  • Renaming workstealing --> workrequesting
  • Adding adaptive work stealing (steal half/steal one)
    • this makes this scheduler consistently (albeit only slightly) faster than the (default) local-priority scheduler
  • Adding LIFO and FIFO variations of local work-stealing scheduler
    • flyby: fixing HPX_WITH_SWAP_CONTEXT_EMULATION
    • flyby: minor changes to fibonacci_local example
  • Adding high- and low- priority queues
    • flyby: cache_line_data now does not generate warnings errors if padding is not needed

hkaiser avatar Apr 11 '22 22:04 hkaiser

First performance measurements show an overall improvement of up to 5-10%. Very promising!

hkaiser avatar Apr 13 '22 19:04 hkaiser

Performance test report

HPX Performance

Comparison

BENCHMARKFORK_JOIN_EXECUTORPARALLEL_EXECUTORSCHEDULER_EXECUTOR
For Each(=)(=)+

Info

PropertyBeforeAfter
HPX Commita68196882e3e093ba44367f6675f538d613c9aa3cbd27da156c3f90be367a1ac6dc16704f580002f
HPX Datetime2022-02-09T15:45:06+00:002022-04-13T22:08:13+00:00
Envfile
Hostnamenid00729nid01193
Compiler/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0
Clusternamedaintdaint
Datetime2022-02-09T17:03:21.440240+01:002022-04-14T00:21:45.647786+02:00

Comparison

BENCHMARKNO-EXECUTOR
Future Overhead - Create Thread Hierarchical - Latch(=)

Info

PropertyBeforeAfter
HPX Commit96a2e4bd1c76207dea8d5302784962c927882406cbd27da156c3f90be367a1ac6dc16704f580002f
HPX Datetime2021-11-11T08:14:57+00:002022-04-13T22:08:13+00:00
Envfile
Hostnamenid00006nid01193
Compiler/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0
Clusternamedaintdaint
Datetime2021-11-11T09:28:13.071121+01:002022-04-14T00:22:02.373105+02:00

Comparison

BENCHMARKFORK_JOIN_EXECUTOR_DEFAULT_FORK_JOIN_POLICY_ALLOCATORPARALLEL_EXECUTOR_DEFAULT_PARALLEL_POLICY_ALLOCATORSCHEDULER_EXECUTOR_DEFAULT_SCHEDULER_EXECUTOR_ALLOCATOR
Stream Benchmark - Add-(=)(=)
Stream Benchmark - Scale(=)(=)(=)
Stream Benchmark - Triad-(=)(=)
Stream Benchmark - Copy(=)(=)(=)

Info

PropertyBeforeAfter
HPX Commit71d8dbe40b737be02ea734f9d98fcc0b1e21f01acbd27da156c3f90be367a1ac6dc16704f580002f
HPX Datetime2021-11-10T19:14:21+00:002022-04-13T22:08:13+00:00
Envfile
Hostnamenid00120nid01193
Compiler/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0
Clusternamedaintdaint
Datetime2021-11-10T20:28:18.266961+01:002022-04-14T00:22:17.738365+02:00

Explanation of Symbols

SymbolMEANING
=No performance change (confidence interval within ±1%)
(=)Probably no performance change (confidence interval within ±2%)
(+)/(-)Very small performance improvement/degradation (≤1%)
+/-Small performance improvement/degradation (≤5%)
++/--Large performance improvement/degradation (≤10%)
+++/---Very large performance improvement/degradation (>10%)
?Probably no change, but quite large uncertainty (confidence interval with ±5%)
??Unclear result, very large uncertainty (±10%)
???Something unexpected…

StellarBot avatar Apr 13 '22 22:04 StellarBot

Performance test report

HPX Performance

Comparison

BENCHMARKFORK_JOIN_EXECUTORPARALLEL_EXECUTORSCHEDULER_EXECUTOR
For Each(=)??(=)

Info

PropertyBeforeAfter
HPX Commiteb604d5bfa8744d3c9cb3af402809c54e3d8f4ee8acafff1cbc5bfee4f959786bb01fbdd83613ee2
HPX Datetime2023-01-12T23:07:58+00:002023-01-17T00:53:41+00:00
Clusternamerostamrostam
Datetime2023-01-13T04:10:15.951027-06:002023-01-16T18:59:20.095675-06:00
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Envfile

Comparison

BENCHMARKNO-EXECUTOR
Future Overhead - Create Thread Hierarchical - Latch??

Info

PropertyBeforeAfter
HPX Commiteb604d5bfa8744d3c9cb3af402809c54e3d8f4ee8acafff1cbc5bfee4f959786bb01fbdd83613ee2
HPX Datetime2023-01-12T23:07:58+00:002023-01-17T00:53:41+00:00
Clusternamerostamrostam
Datetime2023-01-13T04:10:31.068958-06:002023-01-16T18:59:39.241756-06:00
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Envfile

Comparison

BENCHMARKFORK_JOIN_EXECUTOR_DEFAULT_FORK_JOIN_POLICY_ALLOCATORPARALLEL_EXECUTOR_DEFAULT_PARALLEL_POLICY_ALLOCATORSCHEDULER_EXECUTOR_DEFAULT_SCHEDULER_EXECUTOR_ALLOCATOR
Stream Benchmark - Add(=)---++
Stream Benchmark - Scale(=)-=
Stream Benchmark - Triad(=)---++
Stream Benchmark - Copy+(=)(=)

Info

PropertyBeforeAfter
HPX Commiteb604d5bfa8744d3c9cb3af402809c54e3d8f4ee8acafff1cbc5bfee4f959786bb01fbdd83613ee2
HPX Datetime2023-01-12T23:07:58+00:002023-01-17T00:53:41+00:00
Clusternamerostamrostam
Datetime2023-01-13T04:10:46.398919-06:002023-01-16T18:59:55.057716-06:00
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Envfile

Explanation of Symbols

SymbolMEANING
=No performance change (confidence interval within ±1%)
(=)Probably no performance change (confidence interval within ±2%)
(+)/(-)Very small performance improvement/degradation (≤1%)
+/-Small performance improvement/degradation (≤5%)
++/--Large performance improvement/degradation (≤10%)
+++/---Very large performance improvement/degradation (>10%)
?Probably no change, but quite large uncertainty (confidence interval with ±5%)
??Unclear result, very large uncertainty (±10%)
???Something unexpected…

StellarBot avatar Jan 17 '23 01:01 StellarBot

Performance test report

HPX Performance

Comparison

BENCHMARKFORK_JOIN_EXECUTORPARALLEL_EXECUTORSCHEDULER_EXECUTOR
For Each(=)+(=)

Info

PropertyBeforeAfter
HPX Datetime2022-05-31T12:57:29+00:002023-01-17T00:53:41+00:00
HPX Commitd5655f89770ba953e8de3ceb349567d5fcb74a958acafff1cbc5bfee4f959786bb01fbdd83613ee2
Compiler/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0
Hostnamenid01193nid01602
Clusternamedaintdaint
Datetime2022-05-31T15:13:01.357969+02:002023-01-17T02:06:30.200230+01:00
Envfile

Comparison

BENCHMARKNO-EXECUTOR
Future Overhead - Create Thread Hierarchical - Latch--

Info

PropertyBeforeAfter
HPX Datetime2022-05-31T12:57:29+00:002023-01-17T00:53:41+00:00
HPX Commitd5655f89770ba953e8de3ceb349567d5fcb74a958acafff1cbc5bfee4f959786bb01fbdd83613ee2
Compiler/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0
Hostnamenid01193nid01602
Clusternamedaintdaint
Datetime2022-05-31T15:13:18.026239+02:002023-01-17T02:06:49.550654+01:00
Envfile

Comparison

BENCHMARKFORK_JOIN_EXECUTOR_DEFAULT_FORK_JOIN_POLICY_ALLOCATORPARALLEL_EXECUTOR_DEFAULT_PARALLEL_POLICY_ALLOCATORSCHEDULER_EXECUTOR_DEFAULT_SCHEDULER_EXECUTOR_ALLOCATOR
Stream Benchmark - Add(=)+(=)
Stream Benchmark - Scale(=)+++(=)
Stream Benchmark - Triad(=)++(=)
Stream Benchmark - Copy(=)++(=)

Info

PropertyBeforeAfter
HPX Datetime2021-11-10T19:14:21+00:002023-01-17T00:53:41+00:00
HPX Commit71d8dbe40b737be02ea734f9d98fcc0b1e21f01a8acafff1cbc5bfee4f959786bb01fbdd83613ee2
Compiler/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0
Hostnamenid00120nid01602
Clusternamedaintdaint
Datetime2021-11-10T20:28:18.266961+01:002023-01-17T02:07:04.830876+01:00
Envfile

Explanation of Symbols

SymbolMEANING
=No performance change (confidence interval within ±1%)
(=)Probably no performance change (confidence interval within ±2%)
(+)/(-)Very small performance improvement/degradation (≤1%)
+/-Small performance improvement/degradation (≤5%)
++/--Large performance improvement/degradation (≤10%)
+++/---Very large performance improvement/degradation (>10%)
?Probably no change, but quite large uncertainty (confidence interval with ±5%)
??Unclear result, very large uncertainty (±10%)
???Something unexpected…

StellarBot avatar Jan 17 '23 01:01 StellarBot

Performance test report

HPX Performance

Comparison

BENCHMARKFORK_JOIN_EXECUTORPARALLEL_EXECUTORSCHEDULER_EXECUTOR
For Each(=)(=)(=)

Info

PropertyBeforeAfter
HPX Datetime2023-01-12T23:07:58+00:002023-01-17T23:18:13+00:00
HPX Commiteb604d5bfa8744d3c9cb3af402809c54e3d8f4ee8759d626bc17c452a49df27c0ccaacd07ff8a2ba
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu
Envfile
Datetime2023-01-13T04:10:15.951027-06:002023-01-17T17:24:37.483620-06:00
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Clusternamerostamrostam

Comparison

BENCHMARKNO-EXECUTOR
Future Overhead - Create Thread Hierarchical - Latch??

Info

PropertyBeforeAfter
HPX Datetime2023-01-12T23:07:58+00:002023-01-17T23:18:13+00:00
HPX Commiteb604d5bfa8744d3c9cb3af402809c54e3d8f4ee8759d626bc17c452a49df27c0ccaacd07ff8a2ba
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu
Envfile
Datetime2023-01-13T04:10:31.068958-06:002023-01-17T17:24:57.417405-06:00
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Clusternamerostamrostam

Comparison

BENCHMARKFORK_JOIN_EXECUTOR_DEFAULT_FORK_JOIN_POLICY_ALLOCATORPARALLEL_EXECUTOR_DEFAULT_PARALLEL_POLICY_ALLOCATORSCHEDULER_EXECUTOR_DEFAULT_SCHEDULER_EXECUTOR_ALLOCATOR
Stream Benchmark - Add---------
Stream Benchmark - Scale-(=)=
Stream Benchmark - Triad---------
Stream Benchmark - Copy(=)----

Info

PropertyBeforeAfter
HPX Datetime2023-01-12T23:07:58+00:002023-01-17T23:18:13+00:00
HPX Commiteb604d5bfa8744d3c9cb3af402809c54e3d8f4ee8759d626bc17c452a49df27c0ccaacd07ff8a2ba
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu
Envfile
Datetime2023-01-13T04:10:46.398919-06:002023-01-17T17:25:14.693108-06:00
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Clusternamerostamrostam

Explanation of Symbols

SymbolMEANING
=No performance change (confidence interval within ±1%)
(=)Probably no performance change (confidence interval within ±2%)
(+)/(-)Very small performance improvement/degradation (≤1%)
+/-Small performance improvement/degradation (≤5%)
++/--Large performance improvement/degradation (≤10%)
+++/---Very large performance improvement/degradation (>10%)
?Probably no change, but quite large uncertainty (confidence interval with ±5%)
??Unclear result, very large uncertainty (±10%)
???Something unexpected…

StellarBot avatar Jan 17 '23 23:01 StellarBot

Performance test report

HPX Performance

Comparison

BENCHMARKFORK_JOIN_EXECUTORPARALLEL_EXECUTORSCHEDULER_EXECUTOR
For Each(=)(=)(=)

Info

PropertyBeforeAfter
HPX Datetime2023-01-12T23:07:58+00:002023-01-27T22:07:35+00:00
HPX Commiteb604d5bfa8744d3c9cb3af402809c54e3d8f4eeb33de189ec2926318f125473a546d331ad69692f
Clusternamerostamrostam
Envfile
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Datetime2023-01-13T04:10:15.951027-06:002023-01-27T16:15:02.694201-06:00

Comparison

BENCHMARKNO-EXECUTOR
Future Overhead - Create Thread Hierarchical - Latch??

Info

PropertyBeforeAfter
HPX Datetime2023-01-12T23:07:58+00:002023-01-27T22:07:35+00:00
HPX Commiteb604d5bfa8744d3c9cb3af402809c54e3d8f4eeb33de189ec2926318f125473a546d331ad69692f
Clusternamerostamrostam
Envfile
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Datetime2023-01-13T04:10:31.068958-06:002023-01-27T16:15:22.315261-06:00

Comparison

BENCHMARKFORK_JOIN_EXECUTOR_DEFAULT_FORK_JOIN_POLICY_ALLOCATORPARALLEL_EXECUTOR_DEFAULT_PARALLEL_POLICY_ALLOCATORSCHEDULER_EXECUTOR_DEFAULT_SCHEDULER_EXECUTOR_ALLOCATOR
Stream Benchmark - Add---(=)
Stream Benchmark - Scale(=)(=)(=)
Stream Benchmark - Triad(=)--+
Stream Benchmark - Copy+(=)(=)

Info

PropertyBeforeAfter
HPX Datetime2023-01-12T23:07:58+00:002023-01-27T22:07:35+00:00
HPX Commiteb604d5bfa8744d3c9cb3af402809c54e3d8f4eeb33de189ec2926318f125473a546d331ad69692f
Clusternamerostamrostam
Envfile
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Datetime2023-01-13T04:10:46.398919-06:002023-01-27T16:15:38.071747-06:00

Explanation of Symbols

SymbolMEANING
=No performance change (confidence interval within ±1%)
(=)Probably no performance change (confidence interval within ±2%)
(+)/(-)Very small performance improvement/degradation (≤1%)
+/-Small performance improvement/degradation (≤5%)
++/--Large performance improvement/degradation (≤10%)
+++/---Very large performance improvement/degradation (>10%)
?Probably no change, but quite large uncertainty (confidence interval with ±5%)
??Unclear result, very large uncertainty (±10%)
???Something unexpected…

StellarBot avatar Jan 27 '23 22:01 StellarBot

Performance test report

HPX Performance

Comparison

BENCHMARKFORK_JOIN_EXECUTORPARALLEL_EXECUTORSCHEDULER_EXECUTOR
For Each(=)(=)(=)

Info

PropertyBeforeAfter
HPX Commitd4827232e3d49d63f41287db1e8b5767b6dbd95fb33de189ec2926318f125473a546d331ad69692f
HPX Datetime2023-01-12T14:41:15+00:002023-01-27T22:07:35+00:00
Compiler/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0
Envfile
Clusternamedaintdaint
Datetime2023-01-12T16:07:32.649261+01:002023-01-27T23:20:48.276107+01:00
Hostnamenid00267nid01192

Comparison

BENCHMARKNO-EXECUTOR
Future Overhead - Create Thread Hierarchical - Latch---

Info

PropertyBeforeAfter
HPX Commitda01e78993b6bb8da476492b2770f1cc3f117995b33de189ec2926318f125473a546d331ad69692f
HPX Datetime2023-01-18T08:41:20+00:002023-01-27T22:07:35+00:00
Compiler/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0
Envfile
Clusternamedaintdaint
Datetime2023-01-18T09:57:57.669847+01:002023-01-27T23:21:09.050482+01:00
Hostnamenid00005nid01192

Comparison

BENCHMARKFORK_JOIN_EXECUTOR_DEFAULT_FORK_JOIN_POLICY_ALLOCATORPARALLEL_EXECUTOR_DEFAULT_PARALLEL_POLICY_ALLOCATORSCHEDULER_EXECUTOR_DEFAULT_SCHEDULER_EXECUTOR_ALLOCATOR
Stream Benchmark - Add(=)(=)(=)
Stream Benchmark - Scale(=)(=)(=)
Stream Benchmark - Triad(=)(=)(=)
Stream Benchmark - Copy(=)(=)(=)

Info

PropertyBeforeAfter
HPX Commit52952d870ab05881c0ef01bde746b95bf5e74ef0b33de189ec2926318f125473a546d331ad69692f
HPX Datetime2023-01-17T08:25:42+00:002023-01-27T22:07:35+00:00
Compiler/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0
Envfile
Clusternamedaintdaint
Datetime2023-01-17T09:44:28.090718+01:002023-01-27T23:21:25.719950+01:00
Hostnamenid00005nid01192

Explanation of Symbols

SymbolMEANING
=No performance change (confidence interval within ±1%)
(=)Probably no performance change (confidence interval within ±2%)
(+)/(-)Very small performance improvement/degradation (≤1%)
+/-Small performance improvement/degradation (≤5%)
++/--Large performance improvement/degradation (≤10%)
+++/---Very large performance improvement/degradation (>10%)
?Probably no change, but quite large uncertainty (confidence interval with ±5%)
??Unclear result, very large uncertainty (±10%)
???Something unexpected…

StellarBot avatar Jan 27 '23 22:01 StellarBot

Performance test report

HPX Performance

Comparison

BENCHMARKFORK_JOIN_EXECUTORPARALLEL_EXECUTORSCHEDULER_EXECUTOR
For Each(=)(=)(=)

Info

PropertyBeforeAfter
HPX Datetime2023-01-12T14:41:15+00:002023-02-09T15:56:58+00:00
HPX Commitd4827232e3d49d63f41287db1e8b5767b6dbd95f46618c749004d3deb99269d404dd58242b89af6f
Hostnamenid00267nid00481
Compiler/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0
Envfile
Datetime2023-01-12T16:07:32.649261+01:002023-02-09T17:15:55.848757+01:00
Clusternamedaintdaint

Comparison

BENCHMARKNO-EXECUTOR
Future Overhead - Create Thread Hierarchical - Latch---

Info

PropertyBeforeAfter
HPX Datetime2023-01-18T08:41:20+00:002023-02-09T15:56:58+00:00
HPX Commitda01e78993b6bb8da476492b2770f1cc3f11799546618c749004d3deb99269d404dd58242b89af6f
Hostnamenid00005nid00481
Compiler/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0
Envfile
Datetime2023-01-18T09:57:57.669847+01:002023-02-09T17:16:16.635277+01:00
Clusternamedaintdaint

Comparison

BENCHMARKFORK_JOIN_EXECUTOR_DEFAULT_FORK_JOIN_POLICY_ALLOCATORPARALLEL_EXECUTOR_DEFAULT_PARALLEL_POLICY_ALLOCATORSCHEDULER_EXECUTOR_DEFAULT_SCHEDULER_EXECUTOR_ALLOCATOR
Stream Benchmark - Add+-(=)
Stream Benchmark - Scale(=)(=)(=)
Stream Benchmark - Triad+-(=)
Stream Benchmark - Copy=(=)(=)

Info

PropertyBeforeAfter
HPX Datetime2023-01-17T08:25:42+00:002023-02-09T15:56:58+00:00
HPX Commit52952d870ab05881c0ef01bde746b95bf5e74ef046618c749004d3deb99269d404dd58242b89af6f
Hostnamenid00005nid00481
Compiler/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0
Envfile
Datetime2023-01-17T09:44:28.090718+01:002023-02-09T17:16:31.551047+01:00
Clusternamedaintdaint

Explanation of Symbols

SymbolMEANING
=No performance change (confidence interval within ±1%)
(=)Probably no performance change (confidence interval within ±2%)
(+)/(-)Very small performance improvement/degradation (≤1%)
+/-Small performance improvement/degradation (≤5%)
++/--Large performance improvement/degradation (≤10%)
+++/---Very large performance improvement/degradation (>10%)
?Probably no change, but quite large uncertainty (confidence interval with ±5%)
??Unclear result, very large uncertainty (±10%)
???Something unexpected…

StellarBot avatar Feb 09 '23 16:02 StellarBot

Performance test report

HPX Performance

Comparison

BENCHMARKFORK_JOIN_EXECUTORPARALLEL_EXECUTORSCHEDULER_EXECUTOR
For Each(=)(=)(=)

Info

PropertyBeforeAfter
HPX Commiteb604d5bfa8744d3c9cb3af402809c54e3d8f4ee46618c749004d3deb99269d404dd58242b89af6f
HPX Datetime2023-01-12T23:07:58+00:002023-02-09T15:56:58+00:00
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu
Envfile
Clusternamerostamrostam
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Datetime2023-01-13T04:10:15.951027-06:002023-02-09T13:06:52.902401-06:00

Comparison

BENCHMARKNO-EXECUTOR
Future Overhead - Create Thread Hierarchical - Latch??

Info

PropertyBeforeAfter
HPX Commiteb604d5bfa8744d3c9cb3af402809c54e3d8f4ee46618c749004d3deb99269d404dd58242b89af6f
HPX Datetime2023-01-12T23:07:58+00:002023-02-09T15:56:58+00:00
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu
Envfile
Clusternamerostamrostam
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Datetime2023-01-13T04:10:31.068958-06:002023-02-09T13:07:13.896342-06:00

Comparison

BENCHMARKFORK_JOIN_EXECUTOR_DEFAULT_FORK_JOIN_POLICY_ALLOCATORPARALLEL_EXECUTOR_DEFAULT_PARALLEL_POLICY_ALLOCATORSCHEDULER_EXECUTOR_DEFAULT_SCHEDULER_EXECUTOR_ALLOCATOR
Stream Benchmark - Add-----++
Stream Benchmark - Scale(=)----
Stream Benchmark - Triad-----++
Stream Benchmark - Copy+---

Info

PropertyBeforeAfter
HPX Commiteb604d5bfa8744d3c9cb3af402809c54e3d8f4ee46618c749004d3deb99269d404dd58242b89af6f
HPX Datetime2023-01-12T23:07:58+00:002023-02-09T15:56:58+00:00
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu
Envfile
Clusternamerostamrostam
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Datetime2023-01-13T04:10:46.398919-06:002023-02-09T13:07:29.646323-06:00

Explanation of Symbols

SymbolMEANING
=No performance change (confidence interval within ±1%)
(=)Probably no performance change (confidence interval within ±2%)
(+)/(-)Very small performance improvement/degradation (≤1%)
+/-Small performance improvement/degradation (≤5%)
++/--Large performance improvement/degradation (≤10%)
+++/---Very large performance improvement/degradation (>10%)
?Probably no change, but quite large uncertainty (confidence interval with ±5%)
??Unclear result, very large uncertainty (±10%)
???Something unexpected…

StellarBot avatar Feb 09 '23 19:02 StellarBot

Performance test report

HPX Performance

Comparison

BENCHMARKFORK_JOIN_EXECUTORPARALLEL_EXECUTORSCHEDULER_EXECUTOR
For Each(=)(=)(=)

Info

PropertyBeforeAfter
HPX Datetime2023-01-12T23:07:58+00:002023-02-09T21:24:49+00:00
HPX Commiteb604d5bfa8744d3c9cb3af402809c54e3d8f4ee94d6c864b7f76f61659af2e267cc995c367c9ccf
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Envfile
Datetime2023-01-13T04:10:15.951027-06:002023-02-09T15:29:19.082860-06:00
Clusternamerostamrostam
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu

Comparison

BENCHMARKNO-EXECUTOR
Future Overhead - Create Thread Hierarchical - Latch??

Info

PropertyBeforeAfter
HPX Datetime2023-01-12T23:07:58+00:002023-02-09T21:24:49+00:00
HPX Commiteb604d5bfa8744d3c9cb3af402809c54e3d8f4ee94d6c864b7f76f61659af2e267cc995c367c9ccf
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Envfile
Datetime2023-01-13T04:10:31.068958-06:002023-02-09T15:29:39.837645-06:00
Clusternamerostamrostam
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu

Comparison

BENCHMARKFORK_JOIN_EXECUTOR_DEFAULT_FORK_JOIN_POLICY_ALLOCATORPARALLEL_EXECUTOR_DEFAULT_PARALLEL_POLICY_ALLOCATORSCHEDULER_EXECUTOR_DEFAULT_SCHEDULER_EXECUTOR_ALLOCATOR
Stream Benchmark - Add(=)-+++
Stream Benchmark - Scale(=)----
Stream Benchmark - Triad(=)-+++
Stream Benchmark - Copy+---

Info

PropertyBeforeAfter
HPX Datetime2023-01-12T23:07:58+00:002023-02-09T21:24:49+00:00
HPX Commiteb604d5bfa8744d3c9cb3af402809c54e3d8f4ee94d6c864b7f76f61659af2e267cc995c367c9ccf
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Envfile
Datetime2023-01-13T04:10:46.398919-06:002023-02-09T15:29:54.427582-06:00
Clusternamerostamrostam
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu

Explanation of Symbols

SymbolMEANING
=No performance change (confidence interval within ±1%)
(=)Probably no performance change (confidence interval within ±2%)
(+)/(-)Very small performance improvement/degradation (≤1%)
+/-Small performance improvement/degradation (≤5%)
++/--Large performance improvement/degradation (≤10%)
+++/---Very large performance improvement/degradation (>10%)
?Probably no change, but quite large uncertainty (confidence interval with ±5%)
??Unclear result, very large uncertainty (±10%)
???Something unexpected…

StellarBot avatar Feb 09 '23 21:02 StellarBot

Performance test report

HPX Performance

Comparison

BENCHMARKFORK_JOIN_EXECUTORPARALLEL_EXECUTORSCHEDULER_EXECUTOR
For Each(=)(=)(=)

Info

PropertyBeforeAfter
HPX Commitd4827232e3d49d63f41287db1e8b5767b6dbd95f94d6c864b7f76f61659af2e267cc995c367c9ccf
HPX Datetime2023-01-12T14:41:15+00:002023-02-09T21:24:49+00:00
Hostnamenid00267nid00979
Compiler/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0
Datetime2023-01-12T16:07:32.649261+01:002023-02-09T22:36:08.679360+01:00
Envfile
Clusternamedaintdaint

Comparison

BENCHMARKNO-EXECUTOR
Future Overhead - Create Thread Hierarchical - Latch---

Info

PropertyBeforeAfter
HPX Commitda01e78993b6bb8da476492b2770f1cc3f11799594d6c864b7f76f61659af2e267cc995c367c9ccf
HPX Datetime2023-01-18T08:41:20+00:002023-02-09T21:24:49+00:00
Hostnamenid00005nid00979
Compiler/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0
Datetime2023-01-18T09:57:57.669847+01:002023-02-09T22:36:28.435260+01:00
Envfile
Clusternamedaintdaint

Comparison

BENCHMARKFORK_JOIN_EXECUTOR_DEFAULT_FORK_JOIN_POLICY_ALLOCATORPARALLEL_EXECUTOR_DEFAULT_PARALLEL_POLICY_ALLOCATORSCHEDULER_EXECUTOR_DEFAULT_SCHEDULER_EXECUTOR_ALLOCATOR
Stream Benchmark - Add+(=)(=)
Stream Benchmark - Scale(=)(=)(=)
Stream Benchmark - Triad+(=)(=)
Stream Benchmark - Copy(=)(=)(=)

Info

PropertyBeforeAfter
HPX Commit52952d870ab05881c0ef01bde746b95bf5e74ef094d6c864b7f76f61659af2e267cc995c367c9ccf
HPX Datetime2023-01-17T08:25:42+00:002023-02-09T21:24:49+00:00
Hostnamenid00005nid00979
Compiler/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0/apps/daint/SSL/HPX/packages/llvm-11.0.0/bin/clang++ 11.0.0
Datetime2023-01-17T09:44:28.090718+01:002023-02-09T22:36:43.289145+01:00
Envfile
Clusternamedaintdaint

Explanation of Symbols

SymbolMEANING
=No performance change (confidence interval within ±1%)
(=)Probably no performance change (confidence interval within ±2%)
(+)/(-)Very small performance improvement/degradation (≤1%)
+/-Small performance improvement/degradation (≤5%)
++/--Large performance improvement/degradation (≤10%)
+++/---Very large performance improvement/degradation (>10%)
?Probably no change, but quite large uncertainty (confidence interval with ±5%)
??Unclear result, very large uncertainty (±10%)
???Something unexpected…

StellarBot avatar Feb 09 '23 21:02 StellarBot

Performance test report

HPX Performance

Comparison

BENCHMARKFORK_JOIN_EXECUTORPARALLEL_EXECUTORSCHEDULER_EXECUTOR
For Each(=)?(=)

Info

PropertyBeforeAfter
HPX Datetime2023-03-06T15:59:25+00:002023-05-05T19:55:05+00:00
HPX Commit6b6e1e71343e80ad04bf610e41c26a41c1f37333e9b45feb2a7ae28d0cd034d6b86e777f95bcc4ce
Datetime2023-03-10T03:27:49.135034-06:002023-05-05T15:36:03.843573-05:00
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu
Envfile
Clusternamerostamrostam

Comparison

BENCHMARKNO-EXECUTOR
Future Overhead - Create Thread Hierarchical - Latch-

Info

PropertyBeforeAfter
HPX Datetime2023-03-06T15:59:25+00:002023-05-05T19:55:05+00:00
HPX Commit6b6e1e71343e80ad04bf610e41c26a41c1f37333e9b45feb2a7ae28d0cd034d6b86e777f95bcc4ce
Datetime2023-03-10T03:28:21.991297-06:002023-05-05T15:36:37.293877-05:00
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu
Envfile
Clusternamerostamrostam

Comparison

BENCHMARKFORK_JOIN_EXECUTOR_DEFAULT_FORK_JOIN_POLICY_ALLOCATORPARALLEL_EXECUTOR_DEFAULT_PARALLEL_POLICY_ALLOCATORSCHEDULER_EXECUTOR_DEFAULT_SCHEDULER_EXECUTOR_ALLOCATOR
Stream Benchmark - Add(=)(=)(=)
Stream Benchmark - Scale(=)(=)(=)
Stream Benchmark - Triad(=)(=)(=)
Stream Benchmark - Copy(=)(=)(=)

Info

PropertyBeforeAfter
HPX Datetime2023-03-06T15:59:25+00:002023-05-05T19:55:05+00:00
HPX Commit6b6e1e71343e80ad04bf610e41c26a41c1f37333e9b45feb2a7ae28d0cd034d6b86e777f95bcc4ce
Datetime2023-03-10T03:28:29.145749-06:002023-05-05T15:36:44.404357-05:00
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu
Envfile
Clusternamerostamrostam

Explanation of Symbols

SymbolMEANING
=No performance change (confidence interval within ±1%)
(=)Probably no performance change (confidence interval within ±2%)
(+)/(-)Very small performance improvement/degradation (≤1%)
+/-Small performance improvement/degradation (≤5%)
++/--Large performance improvement/degradation (≤10%)
+++/---Very large performance improvement/degradation (>10%)
?Probably no change, but quite large uncertainty (confidence interval with ±5%)
??Unclear result, very large uncertainty (±10%)
???Something unexpected…

StellarBot avatar May 05 '23 20:05 StellarBot

@hkaiser Sorry I deleted your feedback with force-push, I remember it though :P I'll let the tests run without the additional logging I had in the previous push, let's see what we get

Pansysk75 avatar Jun 26 '23 23:06 Pansysk75

@Pansysk75 could you please fix the clang-format issues as well?

hkaiser avatar Jun 27 '23 20:06 hkaiser

I started looking at the performance of this scheduler a bit (on the single-NUMA-domain case)

Directly replacing our current scheduler, it performs worse in the general case (at least on the algorithm benchmarks, which I had handy), I also tried using the do_not_combine_tasks hint to bypass the index queues we use on bulk_execute, because that is technically another form of stealing, which would skew the comparison. It is still a bit worse.

In the case of a bulk-execution of relatively uniform work, stealing is very limited, because our scheduling is already quite balanced anyways. So this would explain the performance deficit, as we are possibly taking on a larger overhead (more complex scheduler) for small benefit (a few non-cache-disrupting steals).

And then, there is the fact that we are only able to poll the steal requests in between thread execution, which introduces some latency in responding to steal requests.

I will try to produce a best-case scenario for this scheduler though, even if it is just as a proof of concept.

Edit: it seems to perform much better on few cores, which could suggest a large number of failed stealing attempts when we have many cores. We can experiment with sending the steal request where there is actual work.

Pansysk75 avatar Jun 28 '23 16:06 Pansysk75

I started looking at the performance of this scheduler a bit (on the single-NUMA-domain case)

Directly replacing our current scheduler, it performs worse in the general case (at least on the algorithm benchmarks, which I had handy), I also tried using the do_not_combine_tasks hint to bypass the index queues we use on bulk_execute, because that is technically another form of stealing, which would skew the comparison. It is still a bit worse.

In the case of a bulk-execution of relatively uniform work, stealing is very limited, because our scheduling is already quite balanced anyways. So this would explain the performance deficit, as we are possibly taking on a larger overhead (more complex scheduler) for small benefit (a few non-cache-disrupting steals).

And then, there is the fact that we are only able to poll the steal requests in between thread execution, which introduces some latency in responding to steal requests.

I will try to produce a best-case scenario for this scheduler though, even if it is just as a proof of concept.

Edit: it seems to perform much better on few cores, which could suggest a large number of failed stealing attempts when we have many cores. We can experiment with sending the steal request where there is actual work.

I did see improvements on tests that ran a large amount of separate tasks (like fibonacci). For uniform iterative parallelism the benefit would probably be small.

hkaiser avatar Jun 28 '23 18:06 hkaiser

@hkaiser You'll still have to add the fix in 1d_stencil_8 https://github.com/STEllAR-GROUP/hpx/commit/451bbd02756155e94f2ca04cdfe3fb3695dc6043#diff-126ef56cea5c727b92b9ec59b26d8c429db7f6655405270d63adda430a4a5091 The sem->wait() is not guaranteed to block, so the lambda ends up with a reference to a deleted object.

Pansysk75 avatar Aug 05 '23 22:08 Pansysk75

@hkaiser You'll still have to add the fix in 1d_stencil_8 451bbd0#diff-126ef56cea5c727b92b9ec59b26d8c429db7f6655405270d63adda430a4a5091 The sem->wait() is not guaranteed to block, so the lambda ends up with a reference to a deleted object.

I thought that was fixed by: https://github.com/STEllAR-GROUP/hpx/pull/6294

hkaiser avatar Aug 05 '23 22:08 hkaiser

I thought that was fixed by: #6294

@hkaiser No, I think it cannot be fixed that way (that's why I had gotten a bit confused there). It's a plain old out-of-scope situation. Just think of what happens if the semaphore doesn't need to wait for the sem.signal() (which will often happen, if the semaphore is not "saturated"). The created lambda (probably not executed yet) has a reference to the semaphore, which gets deleted if we go out of scope. There is no way for the semaphore to know it is being referenced this way.

I think that makes sense, unless I have some misconception about the role of sliding_semaphore

Pansysk75 avatar Aug 05 '23 23:08 Pansysk75

@Pansysk75 I have applied the change to the use of the sliding_semaphore everywhere. This however doesn't seem to be sufficient to make things work: https://app.circleci.com/pipelines/github/STEllAR-GROUP/hpx/15639/workflows/eb35fe70-6509-4d54-80a1-3a4454e93d06/jobs/360130

hkaiser avatar Aug 23 '23 14:08 hkaiser

@Pansysk75 I have applied the change to the use of the sliding_semaphore everywhere. This however doesn't seem to be sufficient to make things work: https://app.circleci.com/pipelines/github/STEllAR-GROUP/hpx/15639/workflows/eb35fe70-6509-4d54-80a1-3a4454e93d06/jobs/360130

Seems like tasks get stuck in the stealing queue, re-applying this fix solves the issue: https://github.com/STEllAR-GROUP/hpx/commit/451bbd02756155e94f2ca04cdfe3fb3695dc6043

Did you do something else to try solve that issue, or was this fix accidentally left behind?

Pansysk75 avatar Aug 27 '23 18:08 Pansysk75

@Pansysk75 I have applied the change to the use of the sliding_semaphore everywhere. This however doesn't seem to be sufficient to make things work: https://app.circleci.com/pipelines/github/STEllAR-GROUP/hpx/15639/workflows/eb35fe70-6509-4d54-80a1-3a4454e93d06/jobs/360130

Seems like tasks get stuck in the stealing queue, re-applying this fix solves the issue: 451bbd0

Did you do something else to try solve that issue, or was this fix accidentally left behind?

Thanks a lot - not sure how that got lost. Much appreciated!

hkaiser avatar Aug 27 '23 19:08 hkaiser

Performance test report

HPX Performance

Comparison

BENCHMARKFORK_JOIN_EXECUTORPARALLEL_EXECUTORSCHEDULER_EXECUTOR
For Each(=)??(=)

Info

PropertyBeforeAfter
HPX Datetime2023-05-10T12:07:53+00:002023-08-28T15:47:36+00:00
HPX Commitdcb541576898d370113946ba15fb58c20c8325b2de95b0f4edeccc281067e609f5c8b6cb3492816d
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Datetime2023-05-10T14:50:18.616050-05:002023-08-28T12:31:56.660155-05:00
Clusternamerostamrostam
Envfile
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu

Comparison

BENCHMARKNO-EXECUTOR
Future Overhead - Create Thread Hierarchical - Latch(=)

Info

PropertyBeforeAfter
HPX Datetime2023-05-10T12:07:53+00:002023-08-28T15:47:36+00:00
HPX Commitdcb541576898d370113946ba15fb58c20c8325b2de95b0f4edeccc281067e609f5c8b6cb3492816d
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Datetime2023-05-10T14:52:35.047119-05:002023-08-28T12:34:09.253604-05:00
Clusternamerostamrostam
Envfile
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu

Comparison

BENCHMARKFORK_JOIN_EXECUTOR_DEFAULT_FORK_JOIN_POLICY_ALLOCATORPARALLEL_EXECUTOR_DEFAULT_PARALLEL_POLICY_ALLOCATORSCHEDULER_EXECUTOR_DEFAULT_SCHEDULER_EXECUTOR_ALLOCATOR
Stream Benchmark - Add(=)(=)(=)
Stream Benchmark - Scale(=)(=)=
Stream Benchmark - Triad(=)=(=)
Stream Benchmark - Copy(=)-(=)

Info

PropertyBeforeAfter
HPX Datetime2023-05-10T12:07:53+00:002023-08-28T15:47:36+00:00
HPX Commitdcb541576898d370113946ba15fb58c20c8325b2de95b0f4edeccc281067e609f5c8b6cb3492816d
Compiler/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1/opt/apps/llvm/13.0.1/bin/clang++ 13.0.1
Datetime2023-05-10T14:52:52.237641-05:002023-08-28T12:34:26.236878-05:00
Clusternamerostamrostam
Envfile
Hostnamemedusa08.rostam.cct.lsu.edumedusa08.rostam.cct.lsu.edu

Explanation of Symbols

SymbolMEANING
=No performance change (confidence interval within ±1%)
(=)Probably no performance change (confidence interval within ±2%)
(+)/(-)Very small performance improvement/degradation (≤1%)
+/-Small performance improvement/degradation (≤5%)
++/--Large performance improvement/degradation (≤10%)
+++/---Very large performance improvement/degradation (>10%)
?Probably no change, but quite large uncertainty (confidence interval with ±5%)
??Unclear result, very large uncertainty (±10%)
???Something unexpected…

StellarBot avatar Aug 28 '23 17:08 StellarBot

I think this is good to go now. Thanks again @Pansysk75!

hkaiser avatar Aug 30 '23 15:08 hkaiser

bors merge

hkaiser avatar Aug 30 '23 15:08 hkaiser

Build succeeded!

The publicly hosted instance of bors-ng is deprecated and will go away soon.

If you want to self-host your own instance, instructions are here. For more help, visit the forum.

If you want to switch to GitHub's built-in merge queue, visit their help page.

bors[bot] avatar Aug 30 '23 16:08 bors[bot]