English version

Crible d'Ératosthène sur Risc PC avec StrongARM, version 8

Introduction

Voici 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).

Routines

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:

  1. le nombre N (pour rechercher les nombres premiers de 0 à N²-1),
  2. la taille des blocs (multiple de 480),
  3. un entier nul pour afficher les nombres premiers, ou un entier positif pour avoir le temps d'exécution (c'est alors le nombre d'itérations, plus il est grand, plus c'est précis).
/* 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;
}

Résultats

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.

Téléchargement

Archive contenant le source et le binaire à exécuter depuis la ligne de commande.



Valid XHTML 1.0!
Dernière modification:
webmaster@vinc17.org