- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
For example, I have a 2D array that is 1500x1500 pixels. To use a radix-2 FFT implementation, the typical approach is to pad the array up to 2048x2048 and then run the FFT. But it seems that this is inefficient for MKL. So what would be the most efficient way to perform FFT on such an array?
Thanks.
Link Copied
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
Hi,
The origin of the problem is in the use ofthe set associative L2 cache. Leading dimension a multiple of row size of the cache incurs lots of interference misses (that is, data competing for the same associativity set).
Computing 1500x1500 array with leading dimension 1500 should be close to optimal for MKL. The best padding can be found empiricallywith amicro benchmark that should not be difficult to compose. It might happen that padding to, say, 1634 will be a few percent better.
Thanks,
Dima
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
It is not immediately obvious why 1634 would be better than 1500. The user guide also suggests that for best performance, leading dimension values should be divisible by 16. Neither 1500 nor 1634 satisfy this. Was 1634 determined empircally?
My application needs to run FFT on an arbitrary M x N array. How do I go about arranging my data to get the best performance?
Thanks.
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
Hi,
I mentioned this strange number as an example. In my test it happened to give *slightly better* performance than 1500. So yes it is empirical number.
Re data arrangement the rule is to avoid leading dimension be multiple of 2048. So if M or N (depends on row-major or col-major memory layout you use), are multiple of that number it should be better if the array is padded in that dimension. Otherwise, it should be nearly optimal to not add padding.
Thanks,
Dima
- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page