Veloce a registro sorta di byte?
https://stackoverflow.com/questions/1580686
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Dato un registro di 4 byte (o 16 per SIMD), ci deve essere un modo efficace per ordinare i byte in registro con poche istruzioni.
Grazie in anticipo.
Soluzione
Cercare un efficiente rete di classificazione per n = il numero di byte che ti interessano (4 o 16). Convertire che ad una sequenza di confronto e di scambio istruzioni. (Per n = 16 che sarà più di 'alcuni', però.)
Altri suggerimenti
Trovato! E 'nella carta 2007 "Utilizzo SIMD registri e istruzioni per abilitare Instruction-Level parallelismo in algoritmi di ordinamento" di Furtak, Amaral, e Niewiadomski. Sezione 4.
Si utilizza 4 SSE registra, dispone di 12 punti, e corre in 19 istruzioni, tra cui il carico e memorizzare.
La stessa carta ha un ottimo lavoro per rendere dinamicamente reti di ordinamento con SIMD.
Per velocizzare l'ordinamento delle stringhe, ho finito per imballaggio 7 byte al doppio e l'ordinamento (ranking) di una serie di 16 doppie in SSE2, utilizzando sorta bitonico per creare due percorsi di 8, e una fusione binario per fondere le due piste . Si può 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-bitonico-SSE2-specie-di-16-doppie / (C), e la fase di bitonico merge (se si vuole andare fino in fondo SSE) qui: http://mischasan.wordpress.com/ 2012/11 / 04 / SSE2-odd-even-merge-the-last-step-in-selezione / . Ho sostituito l'ordinamento per inserzione in fondo a qsort con questo tipo, ed è circa 5 volte più veloce qsort dritto. HTH
Non avevo visto la carta UofA; la logica bitonico è da vecchia scuola (CTM) programmazione GPGPU.
Mi dispiace per le stringhe di collegamento incorporato; Non so come aggiungere link cliccabili nei commenti StackOverflow.
Tutti gli algoritmi di ordinamento richiedono "scambiare" i valori da un luogo all'altro. Dal momento che si sta parlando di un registro della CPU letterale, questo significa che qualsiasi tipo avrebbe bisogno di un altro registro da utilizzare come luogo temporaneo per contenere i byte di essere scambiati.
Non ho mai visto un chip con un metodo incorporato per l'ordinamento byte all'interno di un registro. Non dicendo che non è stato fatto, ma non riesco a pensare a molti usi per tale istruzioni.
