<< Chapter < Page Chapter >> Page >

Because the input array references between consecutive leaves are now linear, and like types of leaf sub-transforms are grouped together, it is now possible to compute several leaf sub-transforms in parallel, which is fully described in "Other vector lengths" .

Body sub-transform radix

The radix of the body sub-transforms can be increased in order to reduce the number of passes over the data and make better use of the cache. In practice, the body sub-transform radix is limited by the associativity of the cache as the size of the transform increases. If the radix is greater than the associativity of the nearest level of cache in which a sub-transform cannot fit, there will be cache misses for every iteration of the sub-transform's loop, resulting in severely degraded performance.

All Intel SIMD microprocessors since the Netburst micro-architecture have had at least 8-way associativity in all levels of cache, and thus increasing the radix from 4 to 8 is a sensible decision when targeting Intel machines.

Just as the split-radix 2/4 algorithm requires two different types of leaf sub-transforms, a split-radix 2/8 algorithm would require three, which increases the complexity of statically elaborating and generating code. There is an alternative that does not require implementing three types of leaf sub-transform: where a size- N body sub-transform divides into a size N / 2 body sub-transform and two size N / 4 sub-transforms, the size N and size N / 2 sub-transforms may be collected together and computed as a size-8 sub-transform. Thus the transform is computed with two types of leaf sub-transform and two types of body sub-transform, instead of three types of leaf sub-transform and one type of body sub-transform, as with the standard split-radix 2/8 algorithm.

For the size-128 tranform in [link] , either the sub-transform at line 19 can be subsumed into the sub-transform at line 20, or the sub-transform at line 20 can be subsumed into the sub-transform at line 23 – but not both. The latter choice is better because it involves larger transforms.

CBody *CHardCodedLeaf::find_subsumable_sub_transform(        vector<CNode *>::reverse_iterator i) {   CBody *first = (CBody *)(*i);  i++;  while(i != bs.rend()) {     if(!((*i)->type().compare("body"))) {       CBody *second = (CBody *)(*i);      if(first->N == second->N*2 && first->offset == second->offset){         bs.erase((++i).base());        return second;       }    }     ++i;  }   return NULL;} void CHardCodedLeaf::increase_body_radix(void) {  vector<CNode *>::reverse_iterator ri;   for(ri=bs.rbegin(); ri!=bs.rend(); ++ri) {    if(!((*ri)->type().compare("body"))) {       CBody *n1 = (CBody *)(*ri);      CBody *n2 = find_subsumable_sub_transform(ri);       if(n2) n1->size *= 2;     }  } }
Doubling the radix of body sub-transforms

The code in [link] iterates in reverse over a list of sub-transforms and doubles the radix of the body sub-transforms. Because the list may include multiple types, type introspection at lines 6 and 20 filters out all types that are not body sub-transforms. For each body sub-transform, the increase_body_radix function searches upwards through the list for a subsumable body sub-transform (using find_subsumable_sub_transform ) and if a match is found, the smaller sub-transform is removed from the list, and the size of the larger sub-transform is doubled.

Questions & Answers

what is mutation
Janga Reply
what is a cell
Sifune Reply
how is urine form
Sifune
what is antagonism?
mahase Reply
classification of plants, gymnosperm features.
Linsy Reply
what is the features of gymnosperm
Linsy
how many types of solid did we have
Samuel Reply
what is an ionic bond
Samuel
What is Atoms
Daprince Reply
what is fallopian tube
Merolyn
what is bladder
Merolyn
what's bulbourethral gland
Eduek Reply
urine is formed in the nephron of the renal medulla in the kidney. It starts from filtration, then selective reabsorption and finally secretion
onuoha Reply
State the evolution relation and relevance between endoplasmic reticulum and cytoskeleton as it relates to cell.
Jeremiah
what is heart
Konadu Reply
how is urine formed in human
Konadu
how is urine formed in human
Rahma
what is the diference between a cavity and a canal
Pelagie Reply
what is the causative agent of malaria
Diamond
malaria is caused by an insect called mosquito.
Naomi
Malaria is cause by female anopheles mosquito
Isaac
Malaria is caused by plasmodium Female anopheles mosquitoe is d carrier
Olalekan
a canal is more needed in a root but a cavity is a bad effect
Commander
what are pathogens
Don Reply
In biology, a pathogen (Greek: πάθος pathos "suffering", "passion" and -γενής -genēs "producer of") in the oldest and broadest sense, is anything that can produce disease. A pathogen may also be referred to as an infectious agent, or simply a germ. The term pathogen came into use in the 1880s.[1][2
Zainab
A virus
Commander
Definition of respiration
Muhsin Reply
respiration is the process in which we breath in oxygen and breath out carbon dioxide
Achor
how are lungs work
Commander
where does digestion begins
Achiri Reply
in the mouth
EZEKIEL
what are the functions of follicle stimulating harmones?
Rashima Reply
stimulates the follicle to release the mature ovum into the oviduct
Davonte
what are the functions of Endocrine and pituitary gland
Chinaza
endocrine secrete hormone and regulate body process
Achor
while pituitary gland is an example of endocrine system and it's found in the Brain
Achor
what's biology?
Egbodo Reply
Biology is the study of living organisms, divided into many specialized field that cover their morphology, physiology,anatomy, behaviour,origin and distribution.
Lisah
biology is the study of life.
Alfreda
Biology is the study of how living organisms live and survive in a specific environment
Sifune
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Computing the fast fourier transform on simd microprocessors. OpenStax CNX. Jul 15, 2012 Download for free at http://cnx.org/content/col11438/1.2
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Computing the fast fourier transform on simd microprocessors' conversation and receive update notifications?

Ask