English versionVoici une implémentation en ARM du crible d'Ératosthène, spécialement optimisée pour le Risc PC avec un processeur StrongARM (202 MHz). Avec cette configuration, la bande passante est très faible par rapport à la rapidité du processeur. Après une succession de tests de la version 7 du crible d'Ératosthène, nous avons pu remarquer qu'un programme qui écrit une constante en mémoire (avec le même type d'accès mémoire, i.e. en utilisant le cache par lecture de données non initialisées) est seulement environ 10% plus rapide que la version 7. Nous cherchons donc à:
Contrairement à la version 7, nous ne chercherons pas à utiliser le write buffer au maximum... peut-être dans une future version?
Un article avec plus de détails paraîtra dans le numéro 0C d'ARMada News (revue éditée par l'ARMada, une association française des utilisateurs de machines Acorn).
La routine assembleur se trouve ci-dessous. Vous pouvez l'assembler avec !ObjAsm, après avoir éventuellement remplacé le nom de fichier h:RegNames. Pour l'utiliser, vous pouvez prendre le petit programme C qui se trouve plus loin. Sinon voici comment l'appel se fait pour rechercher les nombres premiers de 0 à N²-1: le registre R0 doit contenir l'entier N (supérieur ou égal à 5), le registre R1 doit contenir l'adresse (multiple of 32) d'un tableau de 32.⌈N²/32⌉ octets, le registre R2 doit contenir l'adresse (multiple of 32) d'un autre tableau (pour des stockages temporaires) et le registre R3 doit contenir la taille des blocs (multiple de 480), inférieure ou égale à 8.π(N), où π(N) est le nombre de nombres premiers inférieurs ou égaux à N. Au retour, les registres ne sont pas modifiés et les N² premiers octets du tableau (R1) indiquent si le nombre correspondant est premier (1) ou non (0).
Note: le format de sortie (tableau d'octets) a été choisi et fixé à
l'avance. On aurait pu avoir une routine plus rapide
si un autre
format de sortie, utilisant moins de mémoire (tableau de bits et/ou
non-stockage des nombres pairs), avait été choisi. Cependant, cela change
le problème, qui est de trouver une optimisation pour un format de sortie
fixé. De toute façon, les mêmes techniques seraient utilisées.
; Crible d'Eratosthène, version 8 (1997-02-11)
; Recherche des nombres premiers jusqu'à N^2-1.
; Entrée:
; R0: entier N >= 5.
; R1: tableau de 32*CEIL(N^2/32) octets. Adresse multiple de 32.
; R2: tableau (données temporaires). Adresse multiple de 32.
; R3: taille d'un bloc (multiple de 480), <= taille(R2) - 8*pi(N).
; Sortie:
; Registres non modifiés.
; Résultats dans R1[0..N^2-1]: 0 (non premier) ou 1 (premier).
GET h:RegNames ;Définit R0, ..., R14, SP, LR.
AREA area_erat, READONLY, CODE, PIC
EXPORT erat
erat STMFD SP!, {R0,R4-R12,LR}
ADR R12, offsets
MOV R11, #0
MOV R10, R2
MLA R5, R0, R0, R1
ADD R4, R2, R3
MOV R0, #0
STR R0, [R4] ;Liste vide.
; Dans la suite:
; R0: 0.
; R1: tableau de booléens (contiendra les résultats).
; R2: bloc où se font les stockages (doit être dans le cache).
; R3: taille du bloc (R2), multiple de 480.
; R4: liste des couples (nombre premier, adresse).
; R5: fin du tableau (R1).
; R6: nombre premier p, en général.
; R9: pointeur sur le bloc (R2).
; R10: adresse du tableau lu pour trouver le prochain nombre premier
; (R2 à la première itération, puis R1).
; R11: offset de l'image du tableau (R1) dans bloc (R2).
; R12: tableau d'offsets.
; Charge le bloc (R2) dans le cache.
MOV R9, R2
load_block LDR R14, [R9], #32 ;32: taille d'une ligne de cache.
CMP R9, R4
BCC load_block
; Initialisation du bloc: suppression des multiples de 2, 3 et 5
; seulement. On stocke: 0100 0001 0001 0100 0101 0001 0000 0101
; 0000 0100 0101 0001 0100 0100 0001... (période)
next_block MOV R9, R2
MOV R8, #&01000000 ;0001.
MOV R6, #&00000100 ;0100.
ORR R7, R8, R6 ;0101.
init_block STMIA R9!, {R6,R8}
STR R8, [R9], #4
STMIA R9!, {R6-R8}
STMIA R9!, {R0,R7}
STMIA R9!, {R0,R6-R8}
STR R6, [R9], #4
STMIA R9!, {R6,R8}
CMP R9, R4
BCC init_block
MOV R8, R4 ;R8: début de la liste
B old_prime ;des (p,adr).
; Supprime les multiples de p dans le bloc.
old_loop STRB R0, [R9], R7, LSL #1 ;Supprime p(30k+1).
CMP R9, R4
BCS old_store1
STRB R0, [R9], R6, LSL #2 ;Supprime p(30k+7).
CMP R9, R4
BCS old_store2
STRB R0, [R9], R6, LSL #1 ;Supprime p(30k+11).
CMP R9, R4
BCS old_store3
STRB R0, [R9], R6, LSL #2 ;Supprime p(30k+13).
CMP R9, R4
BCS old_store4
STRB R0, [R9], R6, LSL #1 ;Supprime p(30k+17).
CMP R9, R4
BCS old_store5
STRB R0, [R9], R6, LSL #2 ;Supprime p(30k+19).
CMP R9, R4
BCS old_store6
STRB R0, [R9], R7, LSL #1 ;Supprime p(30k+23).
CMP R9, R4
BCS old_store7
STRB R0, [R9], R6, LSL #1 ;Supprime p(30k+29).
CMP R9, R4
BCC old_loop
old_store0 STMDB R8, {R6,R9}
old_prime LDMIA R8!, {R6,R9} ;Prochain (p,adr) ou R6 = 0.
ADD R14, PC, R6, LSR #25
BICS R6, R6, #&F8000000 ;C = 1.
SUB R9, R9, R3
CMPNE R9, R4 ;Note: R9 (impair) != R4 (pair).
ADDCC R7, R6, R6, LSL #1 ;R7 = 3p.
SUBCC PC, R14, #4*28
STRNE R9, [R8, #-4]
BNE old_prime
; Nouveaux nombres premiers...
SUB R8, R8, #8
TEQ R8, R4
LDRNE R6, [R8, #-8] ;R6: dernier nombre premier dans la
BNE last_prime ;liste si celle-ci est non vide.
MOV R6, #7 ;Premier nombre premier: 7.
B new_prime
new_loop STRB R0, [R9], R7, LSL #1 ;Supprime p(30k+1).
CMP R9, R4
BCS new_store1
STRB R0, [R9], R6, LSL #2 ;Supprime p(30k+7).
CMP R9, R4
BCS new_store2
STRB R0, [R9], R6, LSL #1 ;Supprime p(30k+11).
CMP R9, R4
BCS new_store3
STRB R0, [R9], R6, LSL #2 ;Supprime p(30k+13).
CMP R9, R4
BCS new_store4
STRB R0, [R9], R6, LSL #1 ;Supprime p(30k+17).
CMP R9, R4
BCS new_store5
STRB R0, [R9], R6, LSL #2 ;Supprime p(30k+19).
CMP R9, R4
BCS new_store6
STRB R0, [R9], R7, LSL #1 ;Supprime p(30k+23).
CMP R9, R4
BCS new_store7
STRB R0, [R9], R6, LSL #1 ;Supprime p(30k+29).
CMP R9, R4
BCC new_loop
new_store0 STMIA R8!, {R6,R9}
last_prime BIC R6, R6, #&F8000000
next_odd ADD R6, R6, #2 ;Nombre impair suivant.
LDRB R14, [R10, R6]
TEQ R14, #0 ;Boucle tant que ce n'est pas
BEQ next_odd ;un nombre premier p.
new_prime MLA R9, R6, R6, R2
LDR R7, [R12, #data-offsets]
SUB R9, R9, R11
MUL R14, R7, R6
CMP R9, R4
LDRCCB R14, [R12, R14, LSR #28]
ADDCC R7, R6, R6, LSL #1 ;R7 = 3p.
SUBCC PC, PC, R14, LSL #2
STR R0, [R8] ;Fin de la liste des (p,adr).
; Recopie le bloc dans le tableau.
MOV R14, R2
ADD R11, R1, R11
copy_block LDMIA R14!, {R6-R9}
STMIA R11!, {R6-R9}
CMP R14, R4
BCC copy_block
CMP R11, R5
SUBCC R11, R11, R1
MOVCC R10, R1
BCC next_block
; Fin.
LDMDB R12, {R8,R9} ;Correction pour les
STMIA R1, {R8,R9} ;entiers de 0 à 7.
LDMFD SP!, {R0,R4-R12,PC}
old_store1 ORR R6, R6, #&18000000
B old_store0
old_store2 ORR R6, R6, #&30000000
B old_store0
old_store3 ORR R6, R6, #&48000000
B old_store0
old_store4 ORR R6, R6, #&60000000
B old_store0
old_store5 ORR R6, R6, #&78000000
B old_store0
old_store6 ORR R6, R6, #&90000000
B old_store0
old_store7 ORR R6, R6, #&A8000000
B old_store0
new_store1 ORR R6, R6, #&18000000
B new_store0
new_store2 ORR R6, R6, #&30000000
B new_store0
new_store3 ORR R6, R6, #&48000000
B new_store0
new_store4 ORR R6, R6, #&60000000
B new_store0
new_store5 ORR R6, R6, #&78000000
B new_store0
new_store6 ORR R6, R6, #&90000000
B new_store0
new_store7 ORR R6, R6, #&A8000000
B new_store0
data DCD &11111111
DCB 0,0,1,1,0,1,0,1
offsets DCB 0,39,27,0,24,0,0,36,21,0,0,33,0,30,18
END
Le programme suivant prend 3 arguments:
/* Crible d'Eratosthène - test et timing
*
* Usage: erat <N> <taille_bloc> <p>
* --> Recherche des nombres premiers jusqu'à N^2-1
* p = 0: affichage
* p > 0: benchmark (nombre d'itérations)
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void erat(int, char *, char *, int);
int ceil32(int x)
{
return (x + 31) & ~31;
}
int main(int argc, char **argv)
{
int i, n, s, p;
char *t, *u;
clock_t start, stop;
if (argc != 4)
exit(1);
if ((n = atoi(argv[1])) < 5)
exit(2);
if ((s = atoi(argv[2])) <= 0 || s % 480)
exit(3);
if ((p = atoi(argv[3])) < 0)
exit(4);
if ((t = malloc(n*(n+8)+s+64)) == NULL)
exit(5);
t = (char *) ceil32((int) t);
u = t + ceil32(n*n);
if (p)
{
start = clock();
for (i = 0; i < p; i++)
erat(n, t, u, s);
stop = clock();
printf("Temps = %.3f ms\n",
(double) (stop-start) * (1000.0/CLK_TCK) / p);
}
else
{
erat(n, t, u, s);
for (i = 0; i < n*n; i++)
if (t[i])
printf("%d\n", i);
}
return 0;
}
Pour N = 1000 (recherche des nombres premiers inférieurs à 1 000 000), avec une taille de blocs de 9600 octets, cela prend 30,8 ms. Noter que c'est très rapide, car l'écriture d'un million d'octets en mémoire par STM prend 24,0 ms, et l'écriture par STR prend 39,9 ms.
Archive contenant le source et le binaire à exécuter depuis la ligne de commande.
