78 val a = (p1._2 - p0._2).scale(1.0 / (p1._1 - p0._1)) |
78 val a = (p1._2 - p0._2).scale(1.0 / (p1._1 - p0._1)) |
79 val b = p0._2 - a.scale(p0._1) |
79 val b = p0._2 - a.scale(p0._1) |
80 Time.ms((a.scale(threads) + b).ms max 0) |
80 Time.ms((a.scale(threads) + b).ms max 0) |
81 } |
81 } |
82 |
82 |
83 val monotone_prefix = sorted_prefix(entries, e => -e._2.ms) |
83 val mono_prefix = sorted_prefix(entries, e => -e._2.ms) |
84 |
84 |
85 val is_mono = entries == monotone_prefix |
85 val is_mono = entries == mono_prefix |
86 val in_prefix = monotone_prefix.length > 1 && threads <= monotone_prefix.last._1 |
86 val in_prefix = mono_prefix.length > 1 && threads <= mono_prefix.last._1 |
87 val in_inflection = !is_mono && threads < entries.drop(monotone_prefix.length).head._1 |
87 val in_inflection = !is_mono && threads < entries.drop(mono_prefix.length).head._1 |
88 if (is_mono || in_prefix || in_inflection) { |
88 if (is_mono || in_prefix || in_inflection) { |
89 // Model with Amdahl's law |
89 // Model with Amdahl's law |
90 val t_p = |
90 val t_p = |
91 Timing_Data.median_time(for { |
91 Timing_Data.median_time(for { |
92 (n, t0) <- monotone_prefix |
92 (n, t0) <- mono_prefix |
93 (m, t1) <- monotone_prefix |
93 (m, t1) <- mono_prefix |
94 if m != n |
94 if m != n |
95 } yield (t0 - t1).scale(n.toDouble * m / (m - n))) |
95 } yield (t0 - t1).scale(n.toDouble * m / (m - n))) |
96 val t_c = |
96 val t_c = |
97 Timing_Data.median_time(for ((n, t) <- monotone_prefix) yield t - t_p.scale(1.0 / n)) |
97 Timing_Data.median_time(for ((n, t) <- mono_prefix) yield t - t_p.scale(1.0 / n)) |
98 |
98 |
99 def model(threads: Int): Time = t_c + t_p.scale(1.0 / threads) |
99 def model(threads: Int): Time = t_c + t_p.scale(1.0 / threads) |
100 |
100 |
101 if (is_mono || in_prefix) model(threads) |
101 if (is_mono || in_prefix) model(threads) |
102 else { |
102 else { |
103 val post_inflection = entries.drop(monotone_prefix.length).head |
103 val post_inflection = entries.drop(mono_prefix.length).head |
104 val inflection_threads = inflection_point(monotone_prefix.last._1, post_inflection._1) |
104 val inflection_threads = inflection_point(mono_prefix.last._1, post_inflection._1) |
105 |
105 |
106 if (threads <= inflection_threads) model(threads) |
106 if (threads <= inflection_threads) model(threads) |
107 else linear((inflection_threads, model(inflection_threads)), post_inflection) |
107 else linear((inflection_threads, model(inflection_threads)), post_inflection) |
108 } |
108 } |
109 } else { |
109 } else { |