6
\$\begingroup\$

I'd like to propose a new winning criterion: Parallelize as much as possible. A challenge of this type is to give a code that involves parallelization.

Let \$T\$ be the running time when run on a single processor. Due to Amdahl's law, as there are more and more processors to be run on, the overall running time will converge to a positive value \$t\$. The submission whose the ratio \$t/T\$ is the smallest shall win.

What are the caveats?

\$\endgroup\$
4
  • \$\begingroup\$ I presume this would have to be something like fastest-algorithm? I could imagine someone intentionally wasting time in parallel to make the inherently serial parts insignificant, if you aren't careful about how you define it. \$\endgroup\$
    – Bbrk24
    Commented May 25, 2023 at 4:00
  • \$\begingroup\$ @Bbrk24 That's what I had in mind as well. Also, this won't mix well with fastest-code because no computer IRL actually has infinitely many processors. \$\endgroup\$
    – Dannyu NDos
    Commented May 25, 2023 at 4:02
  • \$\begingroup\$ Just a idea, consider, maybe, "fastest algorithm assuming infinite parallelism" instead? Might have less loopholes while being easier to describe \$\endgroup\$
    – mousetail 'he-him'
    Commented May 25, 2023 at 15:40
  • 2
    \$\begingroup\$ I second the "fastest algorithm assuming infinite parallelism" definition. In order for this to make sense however you have to define what kind of parallelism constructs there are and how much time they take to execute (e.g. what atomic operations exits). For example, circuit depth would be an objective criterion for a challenge restricted to boolean circuits. \$\endgroup\$
    – AnttiP
    Commented May 29, 2023 at 7:03

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .