6
Dato un registro di 4 byte (o 16 per SIMD), ci deve essere un modo efficiente per ordinare i byte in-register con alcune istruzioni.Tipo di byte in registrazione veloce?
Grazie in anticipo.
A
risposta
5
Cercare un efficiente sorting network per N = il numero di byte che interessa (4 o 16). Convertilo in una sequenza di istruzioni di confronto e scambio. (Per N = 16 che sarà più di "pochi", però.)
1
Tutti gli algoritmi di ordinamento richiedono valori di "scambio" da un luogo a un altro. Dato che stai parlando di un registro di CPU letterale, significa che qualsiasi tipo necessiterà di un altro registro da utilizzare come luogo temporaneo per contenere i byte scambiati.
Non ho mai visto un chip con un metodo incorporato per l'ordinamento dei byte all'interno di un registro. Non dire che non è stato fatto, ma non riesco a pensare a molti usi per una tale istruzione.
+0
Intendevo come ordinare i byte in un registro, ovviamente è necessario utilizzare almeno un altro registro. Scusa per il fraintendimento. – alecco
+0
In realtà c'è un modo per ordinare in-register usando CMPXCHG usando eax register e ruotandolo, come mi ha mostrato un amico che è abbastanza esperto in x86. Poco da guadagnare, ma è possibile. Anche CMPXCHG è piuttosto lento. – alecco
+1
Tutte le architetture SIMD che ho usato hanno tali istruzioni. –
7
Trovato! È nel documento del 2007 "Usare registri SIMD e istruzioni per abilitare il parallelismo a livello di istruzione negli algoritmi di ordinamento" di Furtak, Amaral e Niewiadomski. Sezione 4.
Utilizza 4 registri SSE, ha 12 passaggi e viene eseguito in 19 istruzioni, tra cui carico e archivio.
Lo stesso documento ha un eccellente lavoro per creare dinamicamente reti di ordinamento con SIMD.
+1
Link al PDF: http://www.cs.ualberta.ca/~amaral/papers/furtak-spaa07.pdf – alecco
4
Per accelerare l'ordinamento delle stringhe, ho finito con il confezionamento di 7 byte per doppio e l'ordinamento (classifica) di un array di 16 doppi in SSE2, usando ordinamento bitonico per creare due esecuzioni di 8 e un unione binaria per unire i due piste. Puoi vedere la prima parte qui http://mischasan.wordpress.com/2011/07/29/okay-one-more-poke-at-sse2-sorting-doubles/ (asm) e qui http://mischasan.wordpress.com/2011/09/02/update-on-bitonic-sse2-sort-of-16-doubles/ (C), e il passo di unione bitonica (se vuoi andare SSE fino in fondo) qui: http://mischasan.wordpress.com/2012/11/04/sse2-odd-even-merge-the-last-step-in-sorting/. Ho sostituito il tipo di inserzione in fondo a qsort con questo tipo, ed è circa 5 volte più veloce del qsort diretto. HTH
Non avevo visto il documento UofA; la logica bitonica proviene dalla programmazione GPGPU della vecchia scuola (CTM).
Mi dispiace per le stringhe del collegamento incorporato; Non so come aggiungere link cliccabili nello stackoverflow dei commenti.
Problemi correlati
- 1. Velocità di ricerca del byte [] in byte [] e stringa in stringa - perché quest'ultimo è più veloce?
- 2. Converti byte [] in tipo di buffer
- 3. java tipo di dati byte
- 4. Il modo più veloce di leggere i byte in D2
- 5. tipo di variabile Javascript (byte)
- 6. Golang convertire tipo byte [N] a [] byte
- 7. Confronto tipo più veloce?
- 8. Confronto byte byte per byte, che è più veloce? binario vs bin_collate
- 9. Come convertire il tipo 'byte []' in 'System.Data.Linq.Binary'
- 10. Perché la mia stringa di tipo `byte`?
- 11. Modifica del tipo di stringa in byte in Python 2.7
- 12. come convertire un tipo di valore in byte [] in C#?
- 13. Conteggio veloce del numero di byte uguali tra due array
- 14. Come convertire array di byte in qualsiasi tipo
- 15. Registrazione tipo C++ al trucco della compilazione
- 16. Errori di registrazione PHP in registrazione
- 17. Differenza tra byte vs tipi di dati byte in C#
- 18. Cast veloce in C# usando BitConverter, può essere più veloce?
- 19. Il modo più veloce per convertire un intero in array di byte arbitrariamente ordinati in JavaScript?
- 20. Il modo più veloce per comprimere un elenco di float in byte in python
- 21. Creazione di byte [] in PowerShell
- 22. Converti tipo di dati 'lungo' di array di byte
- 23. Aggiungi byte con tipo casting, Java
- 24. Ordinamento di tipo di matrice di byte rapido
- 25. Lettura veloce di determinati byte di più file in C/C++
- 26. Conversione di pandas.DataFrame in byte
- 27. Tipo di indice di matrice in C#?
- 28. Conversione di sbyte in byte
- 29. rappresentazione di byte in BINARY_CHECKSUM()?
- 30. Impossibile convertire implicitamente il tipo stringa in byte []
Grazie. Sto cercando una soluzione efficiente. Oh, per favore nota che ho detto un "poche istruzioni" e non un "pochi cicli";) – alecco
Ah, vedo che il documento a cui ti sei collegato prende solo questo approccio, usando le istruzioni SSE2. Freddo. –
Sì, non volevo essere troppo prolisso, dato che speravo in una sorta di magia di hackeraggio con asm. In effetti, stavo cercando questa lettura "Implementazione efficiente dell'ordinamento su architettura CPU SIMD multi-core" (Chhugani, .. 2008), ma mi sono frustrato con le istruzioni dell'algoritmo: 1) a) Eseguire In-Register Sort to ottenere sequenze ordinate di lunghezza K. Immagino che per i ricercatori di Intel sia una procedura "duh", ma non per me! (Non sono ancora sicuro che facciano l'intera procedura di istruzione 17-19 per ordinare un registro.) [Nota: mi dispiace, non ho votato per mancanza di karma] – alecco