Sistemi paralleli VLSI.

La tecnologia VLSI ha reso possibile la progettazione di architetture ad alte prestazioni da affiancare a sistemi tradizionali per la risoluzione di problemi specifici. In [A2], è progettata un' architettura VLSI capace di ordinare insiemi di $N$ dati utilizzando come modulo di base una rete di confrontatori per l'ordinamento di piccoli insiemi di $p$ interi, con $p \ll N$. La soluzione proposta richiede tempo ottimo $O(\frac{N\log N}{p\log p})$. Il modulo di base per ordinare gli insiemi di $p$ elementi è la ben nota, e non ottima in tempo, Batcher's Bitonic Sort Network. Il risultato di maggior interesse è l'aver ottenuto un algoritmo con prestazioni ottime in tempo pur usando un elemento sub-ottimo per l'ordinamento di piccoli insiemi. L'algoritmo sfrutta una tecnica di sampling (estrazione di un campione) complessa e richiede sofisticate tecniche di pipeline per ottimizzare il tempo di esecuzione.