Quel est le jeu d'instructions minimum requis pour que tout langage d'assemblage soit considéré comme utile?

StackOverflow https://stackoverflow.com/questions/9439001

Question

J'étudie la programmation d'assemblage en général, j'ai donc décidé d'essayer d'implémenter un "microprocesseur virtuel" dans le logiciel, qui a des registres, des drapeaux et des RAM avec lesquels travailler, implémentés avec des variables et des tableaux. Mais depuis que je veux simuler Seul le comportement le plus élémentaire de tout microprocesseur, Je veux créer un langage d'assemblage qui n'a que les instructions essentielles, seulement les instructions sans lesquelles il ne pourrait pas être utile. Je veux dire, il existe des langages d'assemblage qui peuvent faire de la multiplication et échanger des valeurs de registre, etc., mais ces opérations ne sont pas basiques car vous pouvez les implémenter en utilisant des instructions plus simples. Je ne veux pas mettre en œuvre des instructions comme celles-ci.

Je peux imaginer quelques instructions qui (je crois) doivent toujours être présentes dans n'importe quel langage d'assemblage, comme Se déplacer pour déplacer les octets et JP Pour envoyer le pointeur d'instructions à une autre adresse.

Pourriez-vous suggérer un ensemble des instructions d'assemblage les plus fondamentales et les plus essentielles? Merci!

Était-ce utile?

La solution

Eh bien, c'est un sujet très large. Je suppose que vous devez vous familiariser avec Machine d'accès aléatoire. Je ne suis pas un expert, mais il est difficile de dire quelles instructions doivent être prises en charge par ce microprocesseur très basique. Par exemple: la soustraction et la multiplication peuvent être simulées par opération d'addition. La multiplication est possible si le microprocesseur prend en charge les sauts et les instructions conditionnelles et que la soustraction est possible en ajoutant un nombre négatif.

Autres conseils

Les structures de contrôle comprennent la fonction de base sans laquelle il n'y a pas de langue. Cela signifie que votre langue doit fournir des opérations arithmétiques sur deux variables; Et puis permettez à un programme de modifier le compteur du programme - c'est-à-dire à la branche - en fonction du résultat d'une opération. Très souvent, l'opération cruciale est sub, pour soustraire un opérande d'un autre. Et les conditions sur lesquelles vous autorisez une branche sont:

  1. Le résultat est nul;
  2. Le résultat est supérieur à zéro;
  3. Le résultat est inférieur à zéro.
  4. Aucune condition, c'est-à-dire, branche inconditionnelle

Vous avez également besoin d'instructions pour déplacer les données: Charger et stocker, par exemple.

Ces trois conditions et leurs branches (ou sauts correspondantes, ce qui est une autre façon de le faire) est nécessaire pour tout programme. Non seulement cela, mais juste ces trois opérations simples plus les instructions de déplacement des données, sont suffisantes pour faire n'importe quoi dans un programme sauf E / S. Si vous le vouliez et que vous avez donné une organisation de mémoire coopérante, vous pouvez réécrire Linux en utilisant Just Load, Store, Add, Sub et les trois branches conditionnelles.

Le PDP-8 était une machine beaucoup plus puissante que ceci: il avait un Ensemble riche de huit instructions, y compris les E / S.

Hth

Étonnamment, il y a une chose telle qu'un ONDERNEMENT ONE INSTRUCTION.

Le moindre ensemble d'instructions nécessite Aucune instruction ou peut-être zéro instruction. Je ne sais pas s'ils étaient venus dans de vrais appareils ou non, mais le ONDERNEMENT ONE INSTRUCTION (OISC) a été mis en place et courir avec succès dans Ordinateurs de nanotubes de carbone et Maxq.

En fait, X86 peut également être utilisé comme architecture OISC car c'est possible de faire n'importe quoi avec juste un seul mov Parce que ça a été s'est avéré être Turing-complete. Il y a même un compilateur nommé movfuscator Pour compiler le code C valide dans un programme avec uniquement des mouvements (ou uniquement de XOR, Sub, ADD, XADD, ADC, SBB et / ou, push / pop, changements 1 bits ou CMPXCHG / XCHG)

Cependant, une architecture devrait être "rapidement" assez (ou ne nécessite pas trop d'instructions comme l'OISC pour une tâche par rapport à d'autres architectures) être considéré comme utile.

Les types d'instructions les plus élémentaires pour un ordinateur sont les mouvements de données, les opérations logiques / arithmétiques et la ramification. Pour les opérations arithmétiques, juste un add/subtract est assez. Pour la logique, nous pouvons calculer toutes les fonctions avec seulement un NOR ou NAND, donc un seul est nécessaire. Pour sauter, nous en aurons besoin jump on "<=" ou jump on "<" instruction. Les mouvements de données peuvent être émulés par Add / Sub. Comme ça, nous pouvons utiliser 2 bits pour coder 3 opcodes (add, nand, jump on "<=") et laisser un pour une expansion future. Mais comme cela n'a pas de séparation Instructions de chargement / stockage, il doit fonctionner directement sur un grand fichier de registre au lieu de la mémoire, ou les instructions doivent avoir la possibilité d'utiliser la mémoire comme opérandes.

Si plus de vitesse est nécessaire, une logique supplémentaire, des instructions de ramification et éventuellement un chargement / stockage peuvent être ajoutées, augmentant l'espace OPCode à 3 bits. L'ensemble d'instructions peut être:

  1. charger
  2. boutique
  3. ajouter
  4. et
  5. ni
  6. sauter sur moins de
  7. sauter sur égal

Le changement de gauche peut être effectué avec add Mais le shift droit est plus délicat, vous voudrez peut-être également ajouter un bon changement pour soulager certaines opérations communes

Vous pouvez survivre parfaitement bien avec un ensemble d'instructions minimal composé uniquement de SOB: soustrayez-en un et de la branche. Des programmes entiers peuvent et ont été écrits avec cela.

Regardez les implémentations commerciales

La meilleure réponse est susceptible d'examiner les implémentations commerciales existantes.

Tout ce qui n'est pas vendu commercialement ne devrait pas être utile.

Quelle est la définition d'une instruction?

Par exemple, je pourrais effectuer une instruction qui implémente l'algorithme Unzip, basé sur une implémentation matérielle de Unzip, et ce serait bien sûr la machine la plus efficace possible pour se décompresser.

Serait-il cependant attrayant commercialement? Peu probable, car ce matériel serait probablement trop spécialisé pour justifier le coût de développement.

Mais il y a beaucoup plus de cas nuancé que celle extrême, et la réponse variera probablement avec les technologies concurrentes existantes et la demande du marché dans le temps pour aggraver les choses.

En fin de compte, le "matériel efficace" signifie:

  • Prenez un ensemble de repères, attribuez un poids d'importance à chacun
  • Écrivez un logiciel optimal qui résout ces repères

Raisons possibles pour lesquelles les ISA très petits Turing peuvent être inefficaces

  • Les quelques instructions qu'ils ont sont très complexes et entraînent des coûts importants à chaque fois qu'ils sont appelés, par exemple, vous ne pouvez pas faire certains Pipelining Optimizaitons
  • La densité de code est très petite, ce qui implique:
    • Les performances peuvent être liées par l'instruction pour aller chercher
    • Pas bon pour les appareils intégrés avec une petite mémoire ROM

Implémentations notables de l'OISC

Il serait intéressant d'analyser ceux qui ont une réponse plus concrète.

movfuscator

https://github.com/xoreaxeaxeax/movfuscator

Compilateur jouet c pour x86 qui utilise uniquement le mov x86 Instructions, montrant de manière très concrète qu'une seule instruction suffit.

L'exhaustivité Turing semble avoir été prouvée dans un article: https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

subleq

OSIC éducatif, mentionné précédemment à https://stackoverflow.com/a/9439153/895245 Mais sans le nom:

Voir également:https://esolangs.org/wiki/Subleq

Voir également

https://softwareensineering.stackexchange.com/questions/230538/what-is-the-absolute-mimum-set-of-instructions-required-to-build-a-turing-comp/325501

Théoriquement, un ordinateur d'instruction unique est possible. Cependant, sur le matériel réel, vous auriez besoin d'un minimum de 4. en supposant une architecture de mémoire uniquement (pas de registres accessibles aux utilisateurs).

MOV MEM1 MEM2 - Copiez le contenu de l'emplacement de la mémoire MEM1 à la mémoire Emplacement MEM2 Laissant MEM1 inchangé

NAND MEM1 MEM2 à MEM3- Effectuez une nand logique bitwise entre les données à MEM1 et MEM2 et écrivez le résultat à MEM3

Bitshiftr mem1 mem2 mem3- bitshift droit les données à mem1 mem2 place et écrire la sortie sur mem3

JMPCond MEM1 MEM2 - Testez le bit le moins significatif à MEM1 et s'il est vrai (1) Sautez à MEM2

Maintenant, il ne sera pas super rapide et il mangera la bande passante de mémoire comme un fou, mais il peut être utilisé pour implémenter une machine virtuelle avec n'importe quel ensemble d'instructions arbitraires. De plus, il existe certaines contraintes de programmation, comme la nécessité de programmer dans toutes les données de démarrage, ou le moins un emplacement de mémoire avec uniquement le LSB réglé sur 1. Les périphériques matériels devront utiliser DMA pour l'accès aux E / S, et si cela est implémenté sur un Harvard Architecture Le programme n'aura pas un accès direct à des choses comme des pointeurs.

Vous voudrez peut-être également rechercher des tours d'exhaustivité.

http://en.wikipedia.org/wiki/Turing_Compleness

http://c2.com/cgi/wiki?TuringComplete

Qu'est-ce que Turing est complet?

Cela signifie qu'une langue est suffisante pour calculer tout ce qui peut être calculé.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top