Logicielsmoto.com

Nous sommes le 28 Mar 2024, 12:07

Heures au format UTC + 1 heure




Poster un nouveau sujet Répondre au sujet  [ 168 messages ]  Aller à la page Précédente  1 ... 8, 9, 10, 11, 12
Auteur Message
MessagePosté: 17 Mar 2021, 10:01 
Hors ligne

Inscription: 21 Fév 2020, 11:38
Messages: 366
Samuel Devulder a écrit:
La table contient les carrés des nombres à multiplier, Si les nombres sont sur 8 bits, la table contient 254 valeurs (abs(A+B) vaut 254 au max avec A/B signés sur 8 bits) et chaque valeur fait 2 octets (carré de 8bits). Occupation mémoire 2*254 octets. Avec du 16 bits cela nous ferait 65534*4 .. 128 ko .. trop gros pour thomson mais impec pour 68000 où le mul est très lent.

A noter que c'est une multiplication signée, chose que le 6809 n'a pas. Il nous faut ajouter du code autour, ce qui nous fait allégrement dépasser les 11 cycles au total:
Code:
sMUL8
   STA  ,-S ; 6
   BGE  sM1 ; 3
   NEGA     ; 2
sM1
   TSTB     ; 2
   BGE  sM2 ; 3
   COM  ,S  ; 6
   NEGB     ; 2
sM2
   MUL      ; 11
   TST  ,S+ ; 8
   BGE  sM3 ; 3
   NEGA     ; 2
   NEGB     ; 2
   SBCA #0  ; 2
sM3
   RTS      ; 5 => total = 57 cycles

Le meilleur code 6502 (C64, ORIC) fait une multiplication (signée) 8x8->16 bits entre 47 et 51 cycles avec un table précalculée de 2ko: https://codebase64.org/doku.php?id=base ... iplication

Comme quoi, même sans MUL, il y a moyen d'être rapide.

D'ailleurs en lisant >>ceci<<, on comprends que pour multiplier x*y en signé revient à multiplier x*y en non-signé, et soustraire x de la partie haute si y<0, et soustraire y si x<0. Il y a moyen de gagner quelques cycles avec cela, mais la routine n'est plus en temps symétrique (x*y est parfois plus rapide que y*x)
Code:
sMUL8
    TSTA        ; 2
    BGE  sM1    ; 3
    STB  ,-S    ; 6
    BGE  sM2    ; 3
    STA  ,-S    ; 6
    MUL         ; 11
    SUBA ,S+    ; 6
    SUBA ,S+    ; 6
    RTS         ; 5 => total 48

sM1 TSTB        ; 2
    BGE  sM3    ; 3
    STA  ,-S    ; 6

sM2 MUL         ; 11
    SUBA ,S+    ; 6   
    RTS         ; 5 => total 36 ou 38

sM3 MUL         ; 11
    RTS         ; 5 => total 26 
Le temps minimum est doublé, et le maximum est à peine plus court. Si quelqu'un veut tenter le challenge, ca serait intéressant de voir si on peut faire mieux. :voyons:

(EDIT) J'arrive à un tout petit peut mieux au pire, mais beaucoup moins bon dans le cas du produit de deux nombres entre 0 et 127
Code:
sMUL8
    STD  ,--S   ; 7
    BGE  sM1    ; 3
    TSTB        ; 2
    BGE  sM2    ; 3
    MUL         ; 11
    SUBA ,S+    ; 6
    SUBA ,S+    ; 6
    RTS         ; 5 => 43
   
sM2
    MUL         ; 11
    SUBA  1,S   ; 5
    LEAS  2,S   ; 5
    RTS         ; 5 => 41

sM1 TSTB        ; 2
    BGE  sM3    ; 3
    MUL         ; 11
    SUBA  ,S++  ; 7
    RTS         ; 5 => 38

sM3
    MUL         ; 11
    LEAS  2,S   ; 5
    RTS         ; 5 => 36
Ca reste quand même entre 3x et 4x la vitesse du MUL non signé.



Je sais tout cela

Pour la multiplication signée... Ya juste qu'à utiliser un drapeau 0 ou 1 pour le signé, on sait que - x - = + etc...
Désolé mais je reste sur l'instruction MUL (même sur la version 68000 etc) qui me paraissent vraiment importantes dans pas mal d'opération. Le fait que l'Hitachi 6309 puisse faite des MUL et DIV sur 32 bits, c'st vraiment top (et ça gagne x4 en vitesse comparé à la même opération sur 6809 avec les MUL)

Pour ce qui est du 6502, je le sais aussi c'est même l'objet de mon prochain cours vidéo (et division idem). C'est même grâce à cette routine que les complexité algorithmique sont largement meilleure en utilisant la multiplication (exemple, somme de (i) de 1 à B = N*(N+1)/2. J'ai vu une routine ASS 6809 qui est même plus optimale que sur le 6502 (normal!! Puisque le 6809 a 2 régistres qui, cumulées, donne le D)

Tu peux voir ce que ça donne en assembleur en faisant N sommes et en utilisant la routine de décalage des bits et addition... Ya pas photo. Et dire que le MUL du 6809 divise par 4 le temps de cet algorithme optimisé est un énorme +.

La complexité algorithmique est le sujet majeur de tous les chercheurs en informatique. Ya des cas où cette simplification est possible (notamment avec Somme(i^k)) quelle que soit le "k", il existe une formule qui simplifie le calcul avec des multiplications, et ya des cas où la simplification est impossible (quand on a des variable linéairement indépendantes, comme c'est le cas des polynomes, ou équation différentielles, c'est aussi le cas par exemple, pour la recherche chemins de labyrinthe, pas possibilité de simplifier)

On parle bcp en ce moment des ordinateurs quantiques, d'après ce que je comprends, ces ordinateur seraient capable de fare N opération parallèle sans perte de temps (ce qui n'est pas le cas avec les processeurs actuel)


Haut
 Profil  
Répondre en citant le message  
MessagePosté: 17 Mar 2021, 10:04 
Hors ligne

Inscription: 21 Fév 2020, 11:38
Messages: 366
Ce qui est drôle dans ta démarche est que tu utilises l'instruction MUL pour créer ta matrice, et la formule me parait compliquée (complexité supérieure) à la simple multiplication... qu'elle soit signée ou pas (en utilisant un simple drapeau, genre "signe1" XOR "signe2" avec bit à 1 si négatif...


Haut
 Profil  
Répondre en citant le message  
MessagePosté: 17 Mar 2021, 15:15 
Hors ligne

Inscription: 21 Aoû 2006, 09:06
Messages: 1802
Localisation: Brest
Neotenien a écrit:
Ce qui est drôle dans ta démarche est que tu utilises l'instruction MUL pour créer ta matrice, et la formule me parait compliquée (complexité supérieure) à la simple multiplication... qu'elle soit signée ou pas (en utilisant un simple drapeau, genre "signe1" XOR "signe2" avec bit à 1 si négatif...

Essaye de faire "rapidement" A XOR B (A,B les registres 6809). C'est plus que dur car il faut passer par la mémoire qui mange un max de cycles. Et ce n'est pas tout d'avoir le signe du résultat, il faut calculer les valeurs absolue des deux entrées, et calculer l'opposé de l'entier 16bits en sortie. Pour moi l'algo ci-dessus issus du C64 est vraiment bien foutu car il économise toutes ces opérations. Il peut se généraliser facilement pour faire du 16x16->32 bits signé.

Sinon le "coding chalenge" de faire une multiplication signée 8x8 -> 16bits signés sur thomson en moins de 43 cycles est toujours ouverte. (Truc: il y a l'algo de multiplication de Booth qui existe et qui réalise une multiplication signée dont le temps n'est pas directement proportionnel à la taille des entrées, mais je n'en ai pas encore vu d'implémentation efficace 6809)

_________________
Good morning, that's a nice Tnetennba


Haut
 Profil  
Répondre en citant le message  
Afficher les messages postés depuis:  Trier par  
Poster un nouveau sujet Répondre au sujet  [ 168 messages ]  Aller à la page Précédente  1 ... 8, 9, 10, 11, 12

Heures au format UTC + 1 heure


Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 42 invités


Vous ne pouvez pas poster de nouveaux sujets
Vous ne pouvez pas répondre aux sujets
Vous ne pouvez pas éditer vos messages
Vous ne pouvez pas supprimer vos messages
Vous ne pouvez pas joindre des fichiers

Rechercher:
Aller à:  
cron
Développé par phpBB® Forum Software © phpBB Group
Traduction par phpBB-fr.com