[xeal]

Il discorso sulle SPE come unità "complete" e non solo vettoriali è complesso, ed è valido più sulla carta che nella realtà, nel senso che se vai a guardare i brevetti (data la foglia, brevettare l'albero) e alcuni progetti, di cui però non si sa se verranno mai realizzati, allora vedi che effettivamente una SPE può contenere di tutto. Però, nell'implementazione attuale contiene SOLO 2 unità vettoriali che operano su registri a 128 bit, più la parte relativa al caricamento e alla decodifica delle istruzioni, in questo senso sono complete, ma non general purpose perchè "castrate": sono come le cpu amd o intel a cui togli tutto, ma proprio tutto, anche la cache - comunicano con il local storage con un piccolo controller dma esterno all'unità di calcolo - e lasci, come unità di calcolo, solo la parte per le SSE, oppure come un g4/5 che ha solo (2 unità) altivec. In teoria potrebbero lavorare autonomamente, ma non sono in grado di far girare, ad esempio, il codice di un sistema operativo, quindi devono essere pilotate dalla PPE general purpose. E siccome sono in-order, se capitano due istruzioni dipendenti (ad esempio, A+B e B+C) può usare solo una delle due unità vettoriali (il vantaggio della ooo consiste principalmente in questo: semplificando, anche se posso eseguire solo 2 operazioni alla volta mi preparo ad eseguirne 4-5, così se per caso nelle prime 2 trovo una dipendenza, allora vado a guardare nelle altre se ce n'è qualcuna che posso eseguire indipendentemente, così ho le pipeline sempre piene).

Ma veniamo ad arstechnica: parto dal primo articolo che avevo linkato, che comunque non parla male dell'architettura del Cell, anzi la descrive semplicemente come un approccio alternativo ed interessante, di cui valutare i risultati.

The Cell processor consists of a general-purpose POWERPC processor core connected to eight special-purpose DSP cores. These DSP cores, which IBM calls "synergistic processing elements" (SPE), but I'm going to call "SIMD processing elements" (SPE) because "synergy" is a dumb word, are really the heart of the entire Cell concept.

Ancora:

[quote]The actual architecture of the Cell SPE is a dual-issue, statically scheduled SIMD processor with a large local storage (LS) area. In this respect, the individual SPUs are like very simple, PowerPC 601-era processors.[/qoute]

Qui si potrebbe fare una piccola osservazione: in realtà, il PowerPC 601 è forse il primo processore della famiglia ad aver introdotto una forma moooolto embrionale di logica ooo: visto che possiede/possedeva 2 alu, non aveva senso eseguire le istruzioni strettamente in-order, una dopo l'altra, quindi si effettuava un controllo sulla loro dipendenza, e, se non erano dipendenti, venivano eseguite in parallelo. Le SPU fanno la stessa cosa (ma la logica ooo del 601 dovrebbe essere più complessa di quella dei una spu); ma vediamole più in dettaglio, nella descrizione di arstechnica:

Cell SPE is geared for single-precision SIMD computation. Most of its arithmetic instructions operate on 128-bit vectors of four 32-bit elements.
[salto una parte relativa al local storage, perchè vorrei evitare di impelagarmi anche in quel tipo di discorso]
The SPEs also move the burden of branch prediction and code scheduling into software, much like a VLIW design.

The SPE's very simple front end can take in two instructions at a time, check to see if they can operate in parallel, and then issue them either in parallel or in program order. These two instructions then travel down one of two pipes, "even" or "odd," to be executed. After execution, they're put back in sequence (if necessary) by the very simple commit unit and their results are written back to local memory. The individual SPUs can throw a lot overboard, because they rely on a regular, general-purpose POWERPC processor core to do all the normal kinds of computation that it takes to run regular code. The Cell system features eight of these SPUs all hanging off a central bus, with one 64-bit POWERPC core handling all of the regular computational chores. Thus all of the Cell 's "smarts" can reside either on the PPC core, while the SPUs just do the work that's assigned to them.

Un piccolo appunto: questo articolo è vecchio, è stato scritto subito dopo la presentazione delle spe e prima di conoscere (il giorno dopo) le caratteristiche del core powerpc (che viene enfatizzato molto meno nel secondo articolo, ma ne parliamo dopo).

To sum up, IBM has sort of reapplied the RISC approach of throwing control logic overboard in exchange for a wider execution core and a larger storage area that's situated closer to the execution core. The difference is that instead of the compiler taking up the slack (as in RISC), a combination of the compiler, the programmer, some very smart scheduling software, and a general-purpose CPU do the kind of scheduling and resource allocation work that the control logic used to do

Cioè, la logica ooo viene eliminata per togliere complessità, ecc. ecc., ma questo non vuol dire che un opportuno scheduling non sia necessario: esso viene semplicemente demandato al compilatore (che però può "ragionare" solo in modo generico, non essendo nota la situazione interna al processore nel momento in cui il codice viene eseguito: per questo è nata la logica ooo), al programmatore (ancora peggio), ad un eventuale software di scheduling e al core ppc: cioè, quello che un x86 fa in hardware, il cell lo deve fare (in parte) via software. Da questo punto di vista, anche se più sofisticato, l'approccio del Cell al general purpose (rilevate le debite differenze) è simile a quello dei Crusoe di trasmeta, che non sono certo il massimo della vita quanto a prestazioni (c'è da dire che i crusoe emulano l'architettura x86 con una macchina virtuale, quindi le prestazioni sono basse anche per questo, ma fino a un certo punto: funziona come una specie di jit, quindi alla fine vai ad eseguire del codice nativo). Per chiarezza, il paragone con trasmeta lo trovi anche in quell'articolo.

Once the instructions are in the SPE, the SPE's control unit can issue up to two instructions per cycle, in-order. The SPE has a 128-entry register file (128-bits per entry) that stores both floating-point and integer vectors. As stated above, there are no rename registers. All loop unrolling is done by the programmer/compiler using this very large register file.

Ma veniamo al core "general purpose", che però in quella presentazione non era stato descritto molto in dettaglio:

We do know that this core has a VMX/Altivec unit, at least one FPU, and supports simultaneous multithreading (SMT). It's also in-order issue, like the SPUs. So it appears that this core also lacks an instruction window, presumably for the same reasons that the SPUs do (i.e. to save on die space and cut down on control logic.) I have in my notes that the core is two-issue, like the SPUs, but I can't find this corroborated anywhere else. So it's possible that the core only issues two instructions per cycle peak, i.e. one from each currently-running thread.
[...]
the PPC core does have a VMX unit. Nonetheless, I expect this VMX to be very simple, and roughly comparable to the Altivec unit o the first G4. Everything on this processor is stripped down to the bare minimum, so don't expect a ton of VMX performance out of it, and definitely not anything comparable to the G5. Furthermore, any Altivec code written for the new G4 or G5 would have to be completely reoptimized due to inorder nature of the PPC core's issue

In realtà, al momento della commercializzazione della PS3 il core PPC è stato migliorato, ma non credo vada (molto) oltre il G4e. Da wikipedia:

Cell combines a general-purpose Power Architecture core of modest performance with streamlined coprocessing elements

Forse troverai interessante anche questo (era nella news che ho linkato dopo i 2 articoli):

Yesterday, IBM announced a project that will join forces with Brazilian game developer Hoplon Infotainment to develop a Cell-based mainframe system that will host massively multiplayer online games targeted at console and PC users. IBM is calling this system a "gameframe," and it will use Cell BE coprocessors to handle message passing and physics simulation for a Hoplon-developed MMOG middleware layer, called bitVerse, that the two companies are porting to Cell. The mainframe's general-purpose CPUs (probably POWER, but not specified yet) will handle aspects of the MMOG like logistics, connectivity, and the Websphere- and DB2-driven portions of bitVerse.

The system will be Linux-based, and though this isn't stated, it might be based on the IBM System Cluster 1350, if not identical to it. The System Cluster 1350 is a high-performance computing product with models that integrate the Cell BE as a coprocessor with general-purpose processors from Intel, AMD, or IBM.

Come a dire: per IBM Cell è così general purpose, che lo usa come coprocessore matematico in abbinamento ad altri processori, sia Power, sia x86.

Poi tu dici che nel general purpose va meglio dei processori tradizionali con o senza ooo, e mi fai pensare a certe "sparate" di Kenshi Manabe, della Sony, sparate che, per quanto riguarda il general purpose, su arstechnica definiscono "boriose" senza mezzi termini (full of it). Ti riporto la conclusione:

The consumer demand for Cell-like levels of DSP prowess is limited to gaming right now, and probably will be for a few more years. But the demand for UltraSparc T1-levels of performance per watt is there yesterday in the datacenter. I don't have any kind of insider information at all on this, but I think it's a near certainty that IBM will announce some kind of server-specific version of Cell with an altered, integer-focused SPE architecture as soon as they reasonably can.[nota: sono voci circolate nel 2005, ad oggi non mi risulta che l'architettura di una spe sia stata effettivamente modificata]

This point brings me back to the statement quoted above, and to the issue of whether or not Cell really is "better than" the Pentium line. Manabe's claim is meaningless unless you ask, "better at what?" If Manabe means "better at DSP," then yeah, Cell is certainly better than anything in Intel's current to near-term x86 lineup for that niche. If he means "better at general purpose computing tasks," then, well, he's full of it. And if he means "better at throughput computing applications, like high-volume web servers," then he's either full of it or he's talking about some version of Cell that hasn't been made public yet.

Per quanto riguarda il discorso dei database, mi daresti qualche link? Vorrei capire che algoritmi usano, perchè senza conoscerli posso solo fare delle osservazioni di carattere generale, che potrebbero anche non calzare troppo.

Intanto, il problema principale con gli alberi non sono tanto i salti, quanto piuttosto i frequenti accessi in memoria (che è più lenta, e quindi ti fa perdere tempo, a meno di poter andare avanti con le altre istruzioni, ma questo Cell non lo fa), perchè si tratta di una struttura dati dinamica, con i dati sparsi in memoria, e che per di più va "attraversata" per trovare ciò che si trova, poichè ogni elemento contiene l'indirizzo del successivo (non puoi prendere un elemento a colpo sicuro, ma lo devi cercare). PERO', gli algoritmi che esplorano gli alberi, siccome sono molto importanti, hanno subito nel corso degli anni una notevole ottimizzazione: per citarne una, un albero generico viene sempre trasformato in un albero binario (= ogni nodo ha al massimo due figli), e questo consente, per dati ordinati (o da ordinare), di effettuare algoritmi di ricerca (o di ordinamento) molto veloci, a cui si aggiunge un altro algoritmo, detto di bilanciamento, che consente di avere dei sottoalberi con lo stesso numero di nodi (ogni nodo ha due figli, che a loro volta ne hanno due, e così via), in modo da dividere la, chiamiamola, "area di ricerca" in due parti uguali, dimezzando ulteriormente il tempo di ricerca; il bilanciamento in genere prevede che si conservino a parte delle informazioni, in strutture dati idonee (che possono anche essere degli array), in modo tale e da semplificare le operazioni di bilanciamento, e da velocizzare la ricerca (alla fine, non trovo i dati che mi servono a colpo sicuro, ma quasi).

Per quanto riguarda i database, inoltre, se non ricordo male, una certa parte dell'elaborazione si effettua su dati organizzati in blocchi sequenziali.

Inoltre, una struttura dati, che si chiami "albero", "lista", "pila", "coda", "grafo" ecc., è per lo più un concetto astratto che può essere implementato in modi diversi: quello che ho descritto usa l'impementazione basata sulle "liste concatenate" (che è la versione "concreta" e dinamica del concetto di lista), ma può usare anche vettori (in particolare per le pile, o stack, e le code), o delle matrici (principalmente per i grafi, e un albero è molto simile, come concetto, ad un particolare grafo). Ogni implementazione ha i suoi pro e i suoi contro: ad esempio, nell'uso di vettori/matrici si ha una notevole velocità nell'accesso ai dati, ma una maggiore lentezza se i dati devono essere cancellati (e tolti del tutto, per risparmiare spazio) e/o aggiunti; inoltre, l'occupazione di memoria può essere molto peggiore (specialmente per i grafi "sparsi" e gli alberi). Di conseguenza, gli alberi vengono implementati come struttura dinamica, e non dubito che nei test a cui ti riferisci abbiano usato questo approccio. Aggiungo solo che spesso, nell'esplorare un albero, si fa uso della ricorsione, ovvero si richiama la stessa funzione, ed eseguire delle chiamate a funzioni (con pochi salti al loro interno) può essere meno pesante (anche molto meno) rispetto all'esecuzione di una porzione di codice lunga (= complicata) con molti salti, specialmente in una architettura risc o risc-like (come quella interna delle cpu x86 attuali), con o senza ooo (soprattutto senza, ma anche con).

In definitiva, comunque, ciò che conta maggiormente nei database è la velocità nei calcoli interi, e la possibilità di eseguire in parallelo molte operazioni diverse (= non sugli stessi dati), e su questo, per quanto riguarda Cell, farei un paio di considerazioni.

Innanzi tutto, "apparentemente" Cell ha una notevole potenza di calcolo sugli interi, in virtù delle sue unità SPE vettoriali (2 operazioni ciascuna su 4 interi a 32 bit), però le operazioni necessarie tendono ad essere diverse, quindi non possono essere facilmente vettorializzate, ragion per cui una SPU finisce col poter fare al più 2 operazioni "scalari" (cioè, ogni operando è un solo intero). Per di più, la logica delle due unità SIMD presenti in una SPE effettua anche calcoli in virgola mobile, quindi la circuiteria è più complessa e la singola operazione (un po') più lenta rispetto ad una semplice alu. Ed è per questo che in uno dei quote che ho preso da arstechnica si accenna a cambiamenti nell'architettura delle SPE per trasformarle da unità vettoriali in scalari, per meglio competere, ad esempio, con un UltraSparc (cpu in-order, ma molto "ferrata" nel calcolo intero scalare, che macina database e applicazioni web server alla grande).

D'altra parte (osservazione numero due) ci sono 8 spe, ciascuna delle quali può effetuare una singola transazione, per cui con un po' di sana ottimizzazione e sfruttando tutte le unità in parallelo (e i database si prestano bene a questo tipo di lavoro, anzi ne hanno bisogno), si può ottenere un risultato notevole. In generale, mi aspetto risultati simili con algoritmi parallelizzati a livello di "task", ovvero con dei thread che operano su dati diversi; meno buoni invece se la parallelizzazione prevede la collaborazione delle spe, visto che la loro architettura è pensata principalmente per svolgere compiti autonomi, e le comunicazioni per lo scambio di dati non sono efficientissime, almeno non quanto lo sono gli algoritmi di ispezione della cache e le comunicazioni via hyper transport in un opteron, oppure la condivisione della cache in un Core 2. Se poi vado a confrontare il risultato con un processore tradizionale, dual core monothread, mi aspetto che il cell, con i suoi algoritmi ottimizzati e le 8 spe, vada più veloce; ne sono meno convinto se il confronto vado a farlo con un quad core, oppure con un sistema dual cpu dual core, specialmente se con hyper transport e gestione della memoria NUMA.

Veniamo ai DSP. Innanzi tutto, avevo definito, alla fine, come dsp un processore che, per le sue caratteristiche tecniche, viene sfruttato al meglio con un certo tipo di algoritmi ottimizzati, in particolare su flussi digitali. In origine i dsp non erano vettoriali, ma per lo più eseguivano calcoli scalari su interi: siccome, però la maggior parte di questi calcoli coinvolge operazioni uguali su molte variabili, allora è stato normale trasformarli in unità vettoriali per massimizzarne la velocità di calcolo. Un dsp "puro" ha poi, spesso e volentieri, un'architettura particolare, detta di harvard, con la memoria dati separata dalla memoria di programma, e accede ad entrambe separatamente, per andare ancora più veloce (le cpu "tradizionali" lo fanno di solito con la cache L1), ma sono dettagli.

Le unità vettoriali inserite in una cpu general purpose aggiungono delle funzionalità da dsp, quindi sono parzialmente d'accordo nel dire che diventano ancora più "general". Ma solo parzialmente, perchè le stesse cose poteva farle già prima, solo adesso le fa meglio, quindi, in un certo senso, poichè sono calcoli specializzati, la nostra cpu general purpose si è anche un po' specializzata.

D'altro canto, un dsp può essere molto specializzato, oppure può avere un certo grado di generalità, e quindi può anche essere programmato (con maggiore o minore difficoltà, a seconda dei casi) per compiti meno specifici, al di fuori del campo per cui è stato progettato, ottenendo prestazioni meno buone di quelle che ottiene nel suo campo, ma potenzialmente (anche molto) valide. Alla fine della fiera, parlerei di architetture più o meno ibride general-purpose/dsp, eventualmente sbilanciate verso l'una o l'altra tipologia.

E se un certo processore ha un'architettura tale da eseguire meglio i calcoli tipici di un dsp (come nei test condotti da IBM sul calcolo matriciale, che hanno tirato fuori da Cell il 98% della sua potenza massima teorica!), se la maggior parte delle sue unità di calcolo "assomigliano" a quelle tipiche di un dsp, e se per ottenere buoni risultati nel general purpose deve affidarsi, in tutto o in parte, alle controp@lle del compilatore, ed eventualmente ad una qualche "emulazione" software della logica ooo (perchè se vuoi andare veloce devi riempire tutte le pipeline che lavorano sullo stesso thread, e per farlo spesso sei costretto a riordinare le istruzioni), allora non mi sembra sbagliato parlare di architettura sbilanciata verso il dsp. Oppure, come avevo detto nel post precedente a questo, dire che il processore in questione si comporta prevalentemente come un dsp.

Ma se non vogliamo dire dsp, allora diciamo "streamlined processor", anche se il concetto è simile (per certi versi assomiglia a quello di più dsp che lavorano in parallelo, come fanno le SPE, ma può riferirsi anche al multicore di una cpu tradizionale, anche se "streamlined" ha in sè il concetto dell'elaborazione di un flusso di dati).

Spero di aver messo abbastanza punti