아래가 질문 내용임


---

clrs에 나오는 dp 알고리즘 중에


행렬 곱셈 순서 정해주는 알고리즘 있잖아


이거 만약에 thread가 여러개 있다고 가정하면 문제 어떻게 될까?


예컨대 dp로 풀었을 때 (ABCDE)F 가 가장 곱셈 횟수 적다고 나왔다고 해도


쓰레드 두 개 쓸 때는 fair하게 (ABC)(DEF) 따로 계산하는 게 wall clock time이 더 짧을 수도 잇을 거 아냐


이런 거는 쓸 데 없는 고민임


---


요지는 한 chain이 길어질 경우 idle한 쓰레드가 생기지 않겠냐는 건데


지금 보니 work stealing이나 data processing 쪽에서 얘기하던 straggler 같은 건가 싶기도 하고


 이런 거 formal하게 reasoning하는 거 자체가 별로 의미 없는 짓인가?