3 ms·
He is talking about the fundamental problem of VLIW architectures. They rely on the static scheduling of programs to enable instruction level parallelism -- whi
by DSingularity 13y ago
He is talking about the fundamental problem of VLIW architectures. They rely on the static scheduling of programs to enable instruction level parallelism -- which is critical to performance. Scheduling is an NP Complete problem.
- Dylan16807 13y agoThe harder the problem, the worse it's going to be to calculate it on the fly.
- foxhill 13y agonot true. an OoO scheduler has a fixed window size with which to re-order. and as soon as you have data-dependent branches or dependencies, your compiler cannot possibly schedule instructions effectively.
- Daniel_Newby 13y ago> They rely on the static scheduling ... Or run-time profiling.
- chongli 13y agoHe hasn't said how this would be relevant to the Mill.
- nraynaud 13y agohe proposes backwards scheduling from the sink to the sources inside each function. I don't know how much complexity is that (because np-complete is not that bad when n is low)
- igodard 13y agoScheduling is the bin-packing problem, which is indeed NP. However, long (40+ years) known heuristics get within low single digits % of perfect, and generally better than OOO hardware scheduling because static is not constrained by instruction window size. We didn't invent those heuristics, but they work for us too.