1 Mar
2014
1 Mar
'14
7:49 a.m.
Hi!
I'm currently taking a course in University called "How to write fast numerical
code". We are to do a group project of 3 persons where we choose a numerical
algorithm and optimize it over the course for a particular processor (e.g. apply
vectorization, cache optimization etc...).
I was wondering if there is an interesting algorithm in audio processing that we
could apply. In particular, if there is any library developer out here that
would be interested in an optimization of one of the algorithms used, we would
be happy to contribute. Ideally, the problem is compute intensive (i.e.
bottleneck of algorithm is not the memory hierarchy). FFT is used as an example
in the lecture so it cannot be used, unless there is a significant additional
computation involved.
Thanks very much for suggestions,
Jeremia
1 Mar
1 Mar
11:17 a.m.
Hi Jeremia :)
On Sat, 2014-03-01 at 07:49 +0100, user web210p1 wrote:
FFT is used as an example in the lecture so it cannot
be used, unless
there is a significant additional computation involved.
A less resource hungry JAMin would be nice, by keeping the sound quality
it has got now.
"JAMin uses FFT, so it's a quite CPU and memory hungry beast." -
http://jamin.sourceforge.net/en/reqs.html
An example in a lecture isn't useful for any user. I don't know if
significant additional computation is involved, but JAMin is important
and much used software, not just a theoretical University kindergarten
game, nobody ever would care about.
Regards,
Ralf
1:32 p.m.
On Saturday 01 March 2014 07:27:53 Ralf Mardorf did opine:
Hi Jeremia :)
On Sat, 2014-03-01 at 07:49 +0100, user web210p1 wrote:
I have read, but not tested on big iron, that the "butterfly transform"
gives compatible results with a lot less big iron to do it.
I fooled with it 20 years ago on a big box amiga, it worked, but I couldn't
compare to the same depth of FFT because I couldn't find free FFT that SAS
C-6.58 would build.
FFT is used as an example in the lecture so it
cannot be used, unless
there is a significant additional computation involved.
A less resource hungry JAMin would be nice, by keeping the sound quality
it has got now.
"JAMin uses FFT, so it's a quite CPU and memory hungry beast." -
http://jamin.sourceforge.net/en/reqs.html An example in a lecture isn't useful for any user.
I don't know if
significant additional computation is involved, but JAMin is important
and much used software, not just a theoretical University kindergarten
game, nobody ever would care about.
Regards,
Ralf
_______________________________________________
Linux-audio-dev mailing list
Linux-audio-dev(a)lists.linuxaudio.org
http://lists.linuxaudio.org/listinfo/linux-audio-dev
Cheers, Gene
--
"There are four boxes to be used in defense of liberty:
soap, ballot, jury, and ammo. Please use in that order."
-Ed Howdershelt (Author)
Genes Web page <http://geneslinuxbox.net:6309/gene>
NOTICE: Will pay 100 USD for an HP-4815A defective but
complete probe assembly.
3 Mar
3 Mar
11:44 p.m.
Gene Heskett <gheskett(a)wdtv.com> hat am 1. März 2014 um 13:32 geschrieben:
On Saturday 01 March 2014 07:27:53 Ralf Mardorf did
opine:
After a quick search, I have the impression that "butterfly transform" is
exactly what turns DFT into FFT. Does anybody know some detail whether that's
actually the case?
Hi Jeremia :)
On Sat, 2014-03-01 at 07:49 +0100, user web210p1 wrote:
I have read, but not tested on big iron, that the "butterfly transform"
gives compatible results with a lot less big iron to do it. FFT is used as an example in the lecture so it
cannot be used, unless
there is a significant additional computation involved.
A less resource hungry JAMin would be nice, by keeping the sound quality
it has got now.
"JAMin uses FFT, so it's a quite CPU and memory hungry beast." -
http://jamin.sourceforge.net/en/reqs.html 
4 Mar
4 Mar
1:11 a.m.
On Mon, Mar 03, 2014 at 11:44:13PM +0100, "Jeremia Bär" wrote:
After a quick search, I have the impression that
"butterfly transform" is
exactly what turns DFT into FFT. Does anybody know some detail whether that's
actually the case?
What makes the FFT fast is exploiting some mathematical relations that
allow the DFT to be factored into combinations of simpler transforms,
the sizes of which are factors (integer divisors) of the DFT size. If
the DFT size contains any powers of two, then applying that trick leads
to a solution that will contains two-point transforms, which on a flow
diagram look like a butterfly.
What makes the FFT fast is the factoring trick, the butterflies are
just the result of that if the size contains a power of two. For
example a 125-point FFT will not have any butterflies, it will
consist of combinations of 5-point DFTs.
Ciao,
--
FA
A world of exhaustive, reliable metadata would be an utopia.
It's also a pipe-dream, founded on self-delusion, nerd hubris
and hysterically inflated market opportunities. (Cory Doctorow)
1 Mar
1 Mar
1:33 p.m.
On Sat, Mar 01, 2014 at 11:17:50AM +0100, Ralf Mardorf wrote:
"JAMin uses FFT, so it's a quite CPU and
memory hungry beast." -
That is a very misleading statement. Jamin is a 'CPU and memory
hungry beast' not because it uses FFTs, but because it uses the
wrong algorithm in the first place (which in turn requires the
use of a high overlap factor to hide the resulting problems).
It's not a matter of inefficent coding, but of failed design.
Ciao,
--
FA
A world of exhaustive, reliable metadata would be an utopia.
It's also a pipe-dream, founded on self-delusion, nerd hubris
and hysterically inflated market opportunities. (Cory Doctorow)
3:10 p.m.
On Sat, Mar 1, 2014 at 7:33 AM, Fons Adriaensen <fons(a)linuxaudio.org> wrote:
[...]
in addition, fftw3 has already had years of optimization applied. its name
stands for "fastest fourier transform in the west". there isn't a lot of
point focusing on such core algorithms because they typically have already
been subject to a lot of effort to create an optimized implementation.
2 Mar
2 Mar
9:17 a.m.
[Paul Davis]
On Sat, Mar 1, 2014 at 7:33 AM, Fons Adriaensen
<fons(a)linuxaudio.org> wrote:
[...]
in addition, fftw3 has already had years of optimization applied.
Two algorithms of wide and likely lasting use that might be able to
benefit strongly from vectorisation come to my mind: sample-rate
conversion and time-stretching (the frequency-domain kind which
already benefits from FFTW efficiency but does a lot of costly
arithmetic on top of that). There's excellent code for both out there
but I think -- correct me if I'm wrong -- it's pretty much exclusively
scalar not vector/parallel processing.
Cheers,
Tim
2:25 p.m.
On Sun, Mar 2, 2014 at 3:16 AM, Tim Goetze <tim(a)quitte.de> wrote:
Two algorithms of wide and likely lasting use that
might be able to
benefit strongly from vectorisation come to my mind: sample-rate
conversion and time-stretching (the frequency-domain kind which
already benefits from FFTW efficiency but does a lot of costly
arithmetic on top of that). There's excellent code for both out there
but I think -- correct me if I'm wrong -- it's pretty much exclusively
scalar not vector/parallel processing.
i totally concur.
the OP(s) should by looking at both soundtouch and librubberband. any
others?
8:11 p.m.
[Paul Davis]
the OP(s) should by looking at both soundtouch and
librubberband. any
others?
A few years ago, I've published one which employs Dolson's original
phase vocoder (Richard Dobson's streaming C++ adaptation to be
precise) but I reckon I'm the only one to actually use it. It's only
a command-line application, not a library, doesn't offer means of
changing the time-scaling ratio while processing, and, as I just
notice, its web page is broken rather badly (remind me to install a
"beware of the leopard" sign :). Sound quality though is on par with
the best efforts, I think (not my achievement but Dolson's really).
Tim
1 Mar
1 Mar
1:27 p.m.
On Sat, Mar 01, 2014 at 07:49:18AM +0100, user web210p1 wrote:
I'm currently taking a course in University called
"How to write fast numerical
code". We are to do a group project of 3 persons where we choose a numerical
algorithm and optimize it over the course for a particular processor (e.g. apply
vectorization, cache optimization etc...).
Are you supposed to optimize by
1. understanding the algorithm and the context in which it is used,
and eventually modifying it within given limits on performance,
precision, etc., or
2. only by changing the way it is coded (which seems to be suggested
by your message) ?
In my experience there is much more to be gained from (1) than from
(2), so that is always the first thing I work on.
I've got something you work on but it would have to be treated as
confidential.
Ciao,
--
FA
A world of exhaustive, reliable metadata would be an utopia.
It's also a pipe-dream, founded on self-delusion, nerd hubris
and hysterically inflated market opportunities. (Cory Doctorow)
3 Mar
3 Mar
11:45 p.m.
Hi Fons
Fons Adriaensen <fons(a)linuxaudio.org> hat am 1. März 2014 um 13:27 geschrieben:
Are you supposed to optimize by
1. understanding the algorithm and the context in which it is used,
and eventually modifying it within given limits on performance,
precision, etc., or
2. only by changing the way it is coded (which seems to be suggested
by your message) ?
I'm not sure I get the difference here. As I understand, optimization includes
(1) choice of suitable algorithm for the problem, (2) smart implementation, i.e.
writing code such that the compiler can apply smart optimization (e.g. aliasing)
and (3) optimizing for a particular microarchitecure (leveraging instruction
level paralellism for a fixed CPU model).
If choosing a error bound + approximation algorithm yields acceptable result, I
think that is fine. Is that your point?
I've got something you work on but it would have
to be treated as
confidential.
We will have to submit code to a university-internal repository and it will run
through some software plagiarism system. Would that be a problem?
Thanks,
Jeremia
3713
days inactive
3716
days old
linux-audio-dev@lists.linuxaudio.org
11 comments
7 participants
participants (7)
-
"Jeremia Bär" -
Fons Adriaensen -
Gene Heskett -
Paul Davis -
Ralf Mardorf -
Tim Goetze -
user web210p1