Saturday, May 13, 2006

scheduler

How do we optimally schedule for an FPGA?

One way to look at this problem: we have to schedule circuits A and B with no connection to eachother. Now using only 2 input muxes merge the circuits into one circuit such that if the mux select is 0 then the system behaves as circuit A and if the mux is in 1 then the system behaves as circuit B. Minimize the amount of logic you need without adding new memory elements. The "size" of the resulting circuit tells you how much A and B share.

Another view is to look at processes as using services which are spawn on the array such as a "square-root" or "vector-add" or "increment" or whatever. The a high-volume "square-root" service will need a dedicated subtract and divide service though a low-volume square-root can use a non-dedicated subtract and divide service and simply use flowware to direct the data through the shared resources. The scheduler makes the decisions about "sharing" resources, and also identifies ways of scheduling the transition between processes by the commonality of their resource usage.

I like the idea of improving an algorithm that promotes sharing. It's very fraternal.

No comments: