Re: Circular Convolution scheduler

Piet Delaney
2003-10-14T08:36:43Z

On Tue, 2003-10-07 at 15:19, George Anzinger wrote:
> 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
>
> -g
>
> Clayton Weaver wrote:
> > 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: cgweav@email.com>
> >
> >
>
> --
> George Anzinger george@mvista.com
> 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 majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/
--
piet@www.piet.net