Circular Convolution scheduler
Though the mechanism is doubtless familiar
to signal processing and graphics implementers,
it's probably not thought of much in a
process scheduling contex (although there was
the Evolution Scheduler of a few years ago,
whose implementer may have had something like
circular convolution in mind). It just seems to me
(intuition) that the concept of what circular convolution does is akin to what we've been feeling around for with these ad hoc heuristic
tweaks to the scheduler to adjust for interactivity
and batch behavior, searching for an incremental self-adjusting mechanism that favors interactivity on demand.
I've never implemented a circular convolver in any context, so I was wondering if anyone who
has thinks scheduler prioritization would be simpler if implemented directly as a circular convolution.
(If nothing else, it seems to me that the abstract model of what the schedule prioritizer is doing
would be more coherent than it is with ad hoc
code. This perhaps reduces the risk of unexpected side-effects of incremental tweaks to the scheduler. The behavior of an optimizer that implements an integer approximation of a known mathematical transform when you change its inputs is fairly predictable.)
Regards,
Clayton Weaver
<mailto: [email protected]>
Signature · 6 lines
__________________________________________________________ Sign-up for your own personalized E-mail at Mail.com http://www.mail.com/?sr=signup CareerBuilder.com has over 400,000 jobs. Be smarter about your job search http://corp.mail.com/careers
Ok, I'll admit my ignorance. What is circular convolution? Where can I learn more?
-g
Quoted 29 lines · Clayton Weaver
Though the mechanism is doubtless familiar
to signal processing and graphics implementers,
it's probably not thought of much in a
process scheduling contex (although there was
the Evolution Scheduler of a few years ago,
whose implementer may have had something like
circular convolution in mind). It just seems to me
(intuition) that the concept of what circular convolution does is akin to what we've been feeling around for with these ad hoc heuristic
tweaks to the scheduler to adjust for interactivity
and batch behavior, searching for an incremental self-adjusting mechanism that favors interactivity on demand.I've never implemented a circular convolver in any context, so I was wondering if anyone who
has thinks scheduler prioritization would be simpler if implemented directly as a circular convolution.(If nothing else, it seems to me that the abstract model of what the schedule prioritizer is doing
would be more coherent than it is with ad hoc
code. This perhaps reduces the risk of unexpected side-effects of incremental tweaks to the scheduler. The behavior of an optimizer that implements an integer approximation of a known mathematical transform when you change its inputs is fairly predictable.)Regards,
Clayton Weaver
<mailto: [email protected]>
Signature · 3 lines
George Anzinger [email protected] High-res-timers: http://sourceforge.net/projects/high-res-timers/ Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml
Quoted 2 lines · George Anzinger
Ok, I'll admit my ignorance. What is circular convolution? Where can I learn more?
circular convolution is used with the Fast Fourier Transform. The frequency data goes from -N/2 ...0 ,,,, +N/2, multiplying in the frequency domain is the same as convolving in the time or space domain. The result of multiplying a time series by say a filter is the same as convolving it with the FFT of the filter. Both domains wrap around with the FFT, so the normal convolution associated with the Fourier transform is replace with the circular convolution.
Many prediction algorithms are based on digital signal processing. The Kalman filter for example was used by Harvey for forecasting financial markets. The kernel likely has lots of time series that could be used for system identification for predicting how to best use system resources.
I did a lot of work with them designing Reconstruction algorithms for Brain Scanners.
-piet
Quoted 44 lines
-g
Quoted 29 lines · Clayton Weaver
Though the mechanism is doubtless familiar
to signal processing and graphics implementers,
it's probably not thought of much in a
process scheduling contex (although there was
the Evolution Scheduler of a few years ago,
whose implementer may have had something like
circular convolution in mind). It just seems to me
(intuition) that the concept of what circular convolution does is akin to what we've been feeling around for with these ad hoc heuristic
tweaks to the scheduler to adjust for interactivity
and batch behavior, searching for an incremental self-adjusting mechanism that favors interactivity on demand.I've never implemented a circular convolver in any context, so I was wondering if anyone who
has thinks scheduler prioritization would be simpler if implemented directly as a circular convolution.(If nothing else, it seems to me that the abstract model of what the schedule prioritizer is doing
would be more coherent than it is with ad hoc
code. This perhaps reduces the risk of unexpected side-effects of incremental tweaks to the scheduler. The behavior of an optimizer that implements an integer approximation of a known mathematical transform when you change its inputs is fairly predictable.)Regards,
Clayton Weaver
<mailto: [email protected]>Signature · 9 lines
George Anzinger [email protected] High-res-timers: http://sourceforge.net/projects/high-res-timers/ Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Signature · 1 line
[email protected]
Quoted 9 lines · Piet Delaney
circular convolution is used with the Fast Fourier Transform. The frequency data goes from -N/2 ...0 ,,,, +N/2, multiplying in the frequency domain is the same as convolving in the time or space domain. The result of multiplying a time series by say a filter is the same as convolving it with the FFT of the filter. Both domains wrap around with the FFT, so the normal convolution associated with the Fourier transform is replace with the circular convolution.
Quoted 5 lines
Many prediction algorithms are based on digital signal processing. The Kalman filter for example was used by Harvey for forecasting financial markets. The kernel likely has lots of time series that could be used for system identification for predicting how to best use system resources.
Ok, but what is "circular convolution scheduling"?
-- Jamie
Quoted 11 lines · Jamie Lokier
Quoted 9 lines · Piet Delaney
circular convolution is used with the Fast Fourier Transform. The frequency data goes from -N/2 ...0 ,,,, +N/2, multiplying in the frequency domain is the same as convolving in the time or space domain. The result of multiplying a time series by say a filter is the same as convolving it with the FFT of the filter. Both domains wrap around with the FFT, so the normal convolution associated with the Fourier transform is replace with the circular convolution.
Quoted 10 lines
Quoted 6 lines
Many prediction algorithms are based on digital signal processing. The Kalman filter for example was used by Harvey for forecasting financial markets. The kernel likely has lots of time series that could be used for system identification for predicting how to best use system resources.
Ok, but what is "circular convolution scheduling"?
I don't know anything about it, but I don't see what exactly you'd be trying to predict: the kernel's scheduler _dictates_ scheduling behaviour, obviously. Also, "best use of system resources" wrt scheduling is a big ask considering there isn't one ideal scheduling pattern for all but the most trivial loads, even on a single processor computer (fairness, latency, priority, thoughput, etc). Its difficult to even say one pattern is better than another.
Quoted 7 lines · Nick Piggin
I don't know anything about it, but I don't see what exactly you'd be trying to predict: the kernel's scheduler _dictates_ scheduling behaviour, obviously. Also, "best use of system resources" wrt scheduling is a big ask considering there isn't one ideal scheduling pattern for all but the most trivial loads, even on a single processor computer (fairness, latency, priority, thoughput, etc). Its difficult to even say one pattern is better than another.
Hmm. Prediction is potentially useful.
Instead of an educated ad-hoc pile of heuristics for _dictating_ scheduling behaviour, you can systematically analyse just what is it you're trying to achieve, and design a behaviour which achieves that as closely as possible.
This is where good predictors come in: you feed all the possible scheduling decisions at any point in time into the predictor, and use the output to decide which decision gave the most desired result - taking into account the likelihood of future behaviours. Of course you have to optimise this calculation.
This is classical control theory. In practice it comes up with something like what we have already :) But the design path is different, and if you're very thoroughly analytical about it, maybe there's a chance of avoiding weird corner behaviours that weren't intended.
The down side is that crafted heuristics, like the ones we have, tend to run a _lot_ faster.
-- Jamie
Quoted 11 lines · Jamie Lokier
Quoted 8 lines · Nick Piggin
I don't know anything about it, but I don't see what exactly you'd be trying to predict: the kernel's scheduler _dictates_ scheduling behaviour, obviously. Also, "best use of system resources" wrt scheduling is a big ask considering there isn't one ideal scheduling pattern for all but the most trivial loads, even on a single processor computer (fairness, latency, priority, thoughput, etc). Its difficult to even say one pattern is better than another.
Quoted 7 lines
Hmm. Prediction is potentially useful.
Instead of an educated ad-hoc pile of heuristics for _dictating_ scheduling behaviour, you can systematically analyse just what is it you're trying to achieve, and design a behaviour which achieves that as closely as possible.
Maybe, although as I said, I just don't know what exactly you would predict and what the goals would be.
And often you'll be left with an ad-hoc pile of heuristics driving (or being driven by) your ad-hoc analysis / prediction thingy. Analysing the end result becomes very difficult. See drivers/block/as-iosched.c :P
Quoted 7 lines
This is where good predictors come in: you feed all the possible scheduling decisions at any point in time into the predictor, and use the output to decide which decision gave the most desired result - taking into account the likelihood of future behaviours. Of course you have to optimise this calculation.
Quoted 6 lines
This is classical control theory. In practice it comes up with something like what we have already :) But the design path is different, and if you're very thoroughly analytical about it, maybe there's a chance of avoiding weird corner behaviours that weren't intended.
You still have an ad-hoc starting point because it is not clear what scheduling choices are the best.
Quoted 4 lines
The down side is that crafted heuristics, like the ones we have, tend to run a _lot_ faster.
That too
Quoted 23 lines · Nick Piggin
Quoted 11 lines · Jamie Lokier
Quoted 8 lines · Nick Piggin
I don't know anything about it, but I don't see what exactly you'd be trying to predict: the kernel's scheduler _dictates_ scheduling behaviour, obviously. Also, "best use of system resources" wrt scheduling is a big ask considering there isn't one ideal scheduling pattern for all but the most trivial loads, even on a single processor computer (fairness, latency, priority, thoughput, etc). Its difficult to even say one pattern is better than another.
Quoted 7 lines
Hmm. Prediction is potentially useful.
Instead of an educated ad-hoc pile of heuristics for _dictating_ scheduling behaviour, you can systematically analyse just what is it you're trying to achieve, and design a behaviour which achieves that as closely as possible.
Quoted 19 lines
Maybe, although as I said, I just don't know what exactly you would predict and what the goals would be.
And often you'll be left with an ad-hoc pile of heuristics driving (or being driven by) your ad-hoc analysis / prediction thingy. Analysing the end result becomes very difficult. See
drivers/block/as-iosched.c:PQuoted 12 lines
This is where good predictors come in: you feed all the possible scheduling decisions at any point in time into the predictor, and use the output to decide which decision gave the most desired result - taking into account the likelihood of future behaviours. Of course you have to optimise this calculation.
This is classical control theory. In practice it comes up with something like what we have already :) But the design path is different, and if you're very thoroughly analytical about it, maybe there's a chance of avoiding weird corner behaviours that weren't intended.
I was wondering about an application in user space that monitors various time series within the system. It would periodically perform System Identification by placing the samples
into a matrix and find the cross correlation coefficients by minimizing the noise of their combination. This matrix would then by run in real time, perhaps in the kernel, to crank a Kalman Filter to predict the least squares best estimate for the values of the system time series. Here is where ad-hoc algorithms then use these precicted values to dynamically change the system behavior. I would expect the scheduler and pageout code could do better if they knew that the odds are high that in 10 seconds a huge demand is going to be made on the system memory for example.
Things like effects of lunch and dinner breaks, weekend, holidays, stock market activity, number of servers up, could be combined with the servers time series. System Identification and Kalman filters could be run in Long Term, Medium Term, and Sort Term time frames to predict in these various time frames; similar to how some commodity traders trade in multiple time frames.
You can get very fancy and even add seasonal and non-linear support like Dr.Harvey did at the London School of Economics.
-piet
Quoted 17 lines
Quoted 1 line
You still have an ad-hoc starting point because it is not clear what scheduling choices are the best.
Quoted 4 lines
The down side is that crafted heuristics, like the ones we have, tend to run a _lot_ faster.
That too
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Signature · 1 line
[email protected]
Quoted 47 lines · Piet Delaney
Quoted 24 lines · Nick Piggin
Quoted 12 lines · Jamie Lokier
Quoted 9 lines · Nick Piggin
I don't know anything about it, but I don't see what exactly you'd be trying to predict: the kernel's scheduler _dictates_ scheduling behaviour, obviously. Also, "best use of system resources" wrt scheduling is a big ask considering there isn't one ideal scheduling pattern for all but the most trivial loads, even on a single processor computer (fairness, latency, priority, thoughput, etc). Its difficult to even say one pattern is better than another.
Quoted 8 lines
Hmm. Prediction is potentially useful.
Instead of an educated ad-hoc pile of heuristics for _dictating_ scheduling behaviour, you can systematically analyse just what is it you're trying to achieve, and design a behaviour which achieves that as closely as possible.
Quoted 20 lines
Maybe, although as I said, I just don't know what exactly you would predict and what the goals would be.
And often you'll be left with an ad-hoc pile of heuristics driving (or being driven by) your ad-hoc analysis / prediction thingy. Analysing the end result becomes very difficult. See
drivers/block/as-iosched.c:PQuoted 12 lines
This is where good predictors come in: you feed all the possible scheduling decisions at any point in time into the predictor, and use the output to decide which decision gave the most desired result - taking into account the likelihood of future behaviours. Of course you have to optimise this calculation.
This is classical control theory. In practice it comes up with something like what we have already :) But the design path is different, and if you're very thoroughly analytical about it, maybe there's a chance of avoiding weird corner behaviours that weren't intended.
Quoted 11 lines
I was wondering about an application in user space that monitors
various time series within the system. It would periodically perform System Identification by placing the samples into a matrix and find the cross correlation coefficients by minimizing the noise of their combination. This matrix would then by run in real time, perhaps in the kernel, to crank a Kalman Filter
to predict the least squares best estimate for the values of the
system time series. Here is where ad-hoc algorithms then use these
precicted values to dynamically change the system behavior. I would
expect the scheduler and pageout code could do better if they knew
that the odds are high that in 10 seconds a huge demand is going
to be made on the system memory for example.
I don't expect the scheduler would benefit at all from this sort of future knowledge or knowledge of each task's patterns.
Quoted 9 lines
Things like effects of lunch and dinner breaks, weekend, holidays, stock market activity, number of servers up, could be combined with the servers time series. System Identification and Kalman filters could be run in Long Term, Medium Term, and Sort Term time frames to predict in these various time frames; similar to how some commodity
traders trade in multiple time frames.You can get very fancy and even add seasonal and non-linear support like Dr.Harvey did at the London School of Economics.
I fail to see how this would be simpler or more provably "right" than a manually designed system.
I would rather not continue in this discussion as I'm not at all qualified to give further input, and I'm just speculating. I'd love to see a working implementation though.
In article <[email protected]>,
Nick Piggin <[email protected]> wrote:
| I don't know anything about it, but I don't see what exactly you'd be | trying to predict: the kernel's scheduler _dictates_ scheduling behaviour, | obviously. Also, "best use of system resources" wrt scheduling is a big | ask considering there isn't one ideal scheduling pattern for all but the | most trivial loads, even on a single processor computer (fairness, latency, | priority, thoughput, etc). Its difficult to even say one pattern is better | than another.
I suspect that you've gotten hold of the wrong end of this stick... I would assume that you start by stating which pattern is better, then use the analysis to determine which of the possible actions is most likely to make the pattern match the target. By pattern I mean response vs. throughput, and similar tradeoffs.
This assumes:
- that I understood what the o.p. meant
- that the past is a useful predictor of the future
In any case, I think this scheduler proposal is interesting, I'd love to see a working version.
Signature · 3 lines
bill davidsen <[email protected]> CTO, TMR Associates, Inc Doing interesting things with little computers since 1979.