Intel IXC1100, IXP42X - page 189

Intel® IXP42X Product Line of Network Processors and IXC1100 Control Plane Processor
September 2006 DM
Order Number: 252480-006US 189
Intel XScale® Processor—Intel® IXP42X product line and IXC1100 control plane processors
Unfortunately, prefetch loop unrolling does not work on loops with indeterminate
iterations.
3.10.4.4.8 Pointer Prefetch
Not all looping constructs contain induction variables. However, prefetching techniques
can still be applied. Consider the following linked list traversal example:
The pointer variable p becomes a pseudo induction variable and the data pointed to by
p->next can be pre-fetched to reduce data transfer latency for the next iteration of the
loop. Linked lists should be converted to arrays as much as possible.
Recursive data structure traversal is another construct where prefetching can be
applied. This is similar to linked list traversal. Consider the following pre-order traversal
of a binary tree:
The pointer variable t becomes the pseudo induction variable in a recursive loop. The
data structures pointed to by the values t->left and t->right can be pre-fetched for the
next iteration of the loop.
for(i=0; i<NMAX-2; i++)
{prefetch(data[i+2]);
sum += data[i];
}
sum += data[NMAX-2];
sum += data[NMAX-1];
while(p) {
do_something(p->data);
p = p->next;
}
while(p) {
prefetch(p->next);
do_something(p->data);
p = p->next;
}
preorder(treeNode *t) {
if(t) {
process(t->data);
preorder(t->left);
preorder(t->right);
}
}
preorder(treeNode *t) {
if(t) {
prefetch(t->right);
prefetch(t->left);
process(t->data);
preorder(t->left);
preorder(t->right);
}
}