Author: Gerd Isenberg
Date: 12:09:46 01/04/05
Go up one level in this thread
On January 04, 2005 at 08:43:45, Antonio Senatore wrote:
>
>Hi friends:
>
>I need to find the index of the highest value in an array of N integer positive
>numbers. Does anyone know a faster algorithm than the following:
>
>int find_index (int *arr, int N) {
>
> int best_val = -INF, i, index;
>
> for (i = 0; i < N; i++) {
> if (arr[i] > best_val) {
> index = i;
> best_val = arr[i];
> }
> }
> return index;
>}
>
>Thank you very much in advance
>Antonio
For N <= 2**X (or multiples in an outer loop) and some special coding of the
array entries, there eventually is an branchless brute force SIMD approach.
The X least significant bits of each scored array element contains the array
index itself. That safes to remember the best index so far, but only the max
value is appropriate and allows an efficient SIMD implementation with some
restrictions.
With N <= 64 and arr[]-type of 16-bit short, there remain 10 bits for a score
range of +-512. With SSE2 (P4, AMD64) this could be handled using
PMAXSW-instruction with 128-bit (8*short) xmm registers.
I guess Apples G5 Altivec has similar instructions.
The routine was already posted some time ago, but it seems not yet in the
archives - so one more time SSE2 promoting - about 24 cycles with all in cache.
Gerd
int getMaxOf64(short int s64[] /* aligned 16 */ )
{
__asm
{
mov eax, [s64]
movdqa xmm1, [eax+0*16] ; short 0- 7
movdqa xmm0, [eax+1*16] ; short 8-15
pmaxsw xmm1, [eax+2*16] ; short 16-23
pmaxsw xmm0, [eax+3*16] ; short 24-31
pmaxsw xmm1, [eax+4*16] ; short 32-39
pmaxsw xmm0, [eax+5*16] ; short 40-47
pmaxsw xmm1, [eax+6*16] ; short 48-55
pmaxsw xmm0, [eax+7*16] ; short 56-63
pmaxsw xmm0, xmm1
; horizontal max of all eight words
movdqa xmm1, xmm0
psrldq xmm0, 2 ; one word right
pmaxsw xmm0, xmm1
movdqa xmm1, xmm0
psrldq xmm0, 4 ; two words right
pmaxsw xmm0, xmm1
movdqa xmm1, xmm0
psrldq xmm0, 8 ; four words right
pmaxsw xmm0, xmm1
pextrw eax, xmm0, 0 ; extract the maximum word
cwde ; sign extend 16 to 32 bits
}
}
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.