Ci sono esempi concreti di dove un compilatore paralellizzante fornirebbe un vantaggio in termini di valore? [chiuso]

6

Paul Graham sostiene che:

It would be great if a startup could give us something of the old Moore's Law back, by writing software that could make a large number of CPUs look to the developer like one very fast CPU. ... The most ambitious is to try to do it automatically: to write a compiler that will parallelize our code for us. There's a name for this compiler, the sufficiently smart compiler, and it is a byword for impossibility. But is it really impossible?

Qualcuno può fornire un esempio concreto dove un compilatore paralizzante risolverebbe un punto dolente? Le app Web non sembrano essere un problema: basta eseguire una serie di processi Node. Il raytracing in tempo reale non è un problema: i programmatori stanno scrivendo un linguaggio di assemblaggio multi-thread e SIMD abbastanza felicemente (anzi, alcuni potrebbero lamentarsi se lo rendiamo più facile!). Il Santo Graal deve essere in grado di accelerare qualsiasi programma, sia esso MySQL, Garage Band o Quicken. Sto cercando una via di mezzo:  c'è un problema del mondo reale che hai riscontrato in cui un compilatore "abbastanza intelligente" avrebbe fornito un vantaggio reale, cioè che qualcuno avrebbe pagato per?

Una buona risposta è quella in cui esiste un processo in cui il computer viene eseguito al 100% della CPU su un singolo core per un periodo di tempo doloroso. Quella volta potrebbe essere 10 secondi, se l'attività è destinata a essere veloce. Potrebbe essere di 500 ms se l'attività deve essere interattiva. Potrebbe essere di 10 ore. Per favore descrivi questo problema.

In realtà, questo è tutto ciò che sto cercando: aree candidate per ulteriori indagini . (Quindi, raytracing è fuori dalla lista perché tutti i frutti a bassa attaccatura sono stati banchettati.)

Non mi interessa il motivo per cui non può essere fatto. Ci sono un milione di persone disposte a indicare le ragioni valide per le quali non può essere fatto. Queste risposte non sono utili.

    
posta jamie 20.03.2012 - 22:19
fonte

7 risposte

10

In realtà ho eseguito ray tracing per molti anni. Scrivere il codice SIMD non è lo stesso che utilizzare più core. I compilatori possono ora "vettorizzare" molto codice che in precedenza era stato fatto a mano e utilizzare le istruzioni SIMD. Per i miei sforzi sono andato con OpenMP che permetteva di eseguire i loop esterni in parallelo su molti core (facendo ray per pixel stuff). Questo potrebbe essere fatto automaticamente da un compilatore se ha fatto un sacco di analisi. Si scopre che i thread paralleli accedono tutti alle strutture dati ma non li modificano (senza effetti collaterali), quindi con molta analisi un compilatore potrebbe decidere che i loop possano essere eseguiti contemporaneamente. Di solito non è così e quando lo è probabilmente la gente lo sa comunque.

Poiché le persone hanno difficoltà a creare programmi paralleli, sospetto che sia difficile trovare un algoritmo generale. I casi banali hanno già degli strumenti semplici per aiutare.

Da quello che capisco, i linguaggi funzionali dovrebbero essere più parallelizzabili in quanto presumibilmente non hanno effetti collaterali e nessuno stato. Sembra un sacco di cose che potrebbero essere eseguite in parallelo.

    
risposta data 20.03.2012 - 23:21
fonte
4

L'informatica scientifica ha molti campi in cui i programmi possono essere parallelizzati, ma non facilmente. Un esempio particolare è l'algebra lineare, un'altra dinamica fluidodinamica. I compilatori di parallelizzazione in queste aree sono oggetto di ricerca attiva .

    
risposta data 20.03.2012 - 23:19
fonte
3

Riepilogo:

Non penso che molte persone possano rispondere alla tua domanda perché ci sono alcuni ostacoli piuttosto grandi che ci sono. Consiglierei di studiare la Programmazione Funzionale in generale e Scala in particolare per comprendere a fondo i tipi di scoperte che sono strongmente correlate a ciò che sembra desiderare.

Dettagli:

Per riassumere brevemente la tua domanda, penso che potresti chiederti:

Please tell me about a personal experience I have had where I worked on a problem using traditional single-threaded assumptions where I know that I would experience an improvement with a "magically parallelizing" compiler.

Penso che la sfida sia costituita dalle ipotesi (molte) necessarie per passare da una base di codice a thread singolo presunta esistente alla comprensione di tutte le diverse, complesse e difficili complessità che sono presenti per prendere lo stesso programma e parallelizzarlo accuratamente tramite un compilatore . Questo è un salto non banale, che quasi nessuno può realisticamente realizzare senza aver fatto entrambi i tipi di implementazione.

Detto questo, penso che ci siano alcune pratiche di ingegneria del software che potrebbero aiutarti ad avvicinarti a ciò che potresti cercare. E quello che sento che cercherete è di dedicare il minor tempo possibile a ridisegnare il codice presunto a thread singolo in qualcosa che possa essere facilmente parallelizzato. E questo richiede che tu diventi consapevole di diversi domini di lavoro che lo supporteranno.

  1. Devi scegliere un linguaggio che supporti naturalmente la nozione di codice parallelo.
  2. Il linguaggio deve disporre anche di librerie per le quali la semplice conversione del codice a thread singolo per poter essere multi-thread è una semplice ridenominazione di classe / metodo / funzione.
  3. È necessario assicurarsi che la lingua DEFAULT supporti l'immutabilità e quindi esercitare con fermezza l'immutabilità all'interno di tutti i progetti software presunti a thread singolo.

Se segui tutte e tre queste pratiche, scoprirai la complessità dello spostamento tra codice assunto a thread singolo e parallelamente sarà ridotto drasticamente. In assenza di una qualsiasi delle tre pratiche sopra riportate, troverete gli ostacoli a passare da un singolo thread a un multi-thread per essere così complessi da non valere gli ordini di grandezza dello sforzo extra richiesto. Ed è anche meno probabile che un compilatore possa essere scritto per fare salti detti.

E sto parlando per esperienza personale. Ho iniziato un progetto Java nel 2000 sulla base dello stesso ragionamento che hai usato sopra. Era un sistema di calcolo distribuito ANN / GA (Artificial Neural Network / Genetic Algorithm) per tentare di creare un AI (gioco). Essere una vera sfida, ho iniziato con Checkers per assicurarmi che il mio sistema funzionasse. Per ogni ora di utile lavoro "single-threaded" che ho fatto, ho trascorso altre 99 ore (senza esagerare) su tangenti tecniche non correlate all'obiettivo principale. Alla fine ho ottenuto il mio intero sistema lavorando su 10 nodi. Tuttavia, dopo aver trascorso quasi 2000 ore di lavoro su di esso, ero completamente bruciato nel tentativo di realizzare l'implementazione Go.

Da allora sono tornato a sedermi e sono rimasto molto interessato a come potrei essere in grado di rifare le 2000 ore di lavoro e ridurlo a qualcosa nell'ordine di 20-50 ore. Alla fine ho deciso di inventare la mia lingua e le mie librerie per vedere se potevo risolverlo più velocemente in quel modo. Parli di un enorme tangente tecnico, eh? :)

Subito dopo aver iniziato a generare il mio elenco di requisiti desiderabili nel 2010 / Dic, un mio amico mi ha chiesto perché stavo facendo tutto quel lavoro. E poi ha suggerito di dare un'occhiata a Clojure e Scala. Ho letto velocemente Clojure e non mi è piaciuto quanto rumoroso / boilerplate-ish provenga da Java. Poi leggo su Scala. E non potevo credere che avesse oltre il 60% dei tipi di funzionalità che volevo io stesso. Ho quindi acquistato il nuovo "Programmazione in Scala, 2a edizione" e completamente letto la versione e-reader prima di preso la copia fisica.

Ho passato tutto il tempo tra allora e ora a lavorare duramente per arricchire Scala, Programmazione Funzionale e pensare esclusivamente in termini di immutabilità. È stato piuttosto impegnativo per i miei decenni di esperienza OO. Tuttavia, penso di aver finalmente girato l'angolo su un paio delle principali sfide ... finalmente!

Userò Scala (e Akka, Play e Scala-IDE) e ricreerò completamente il mio sistema AI in modo da poter continuare il mio obiettivo Go? Ci sto giocando adesso. Ho ancora così tanto da imparare e molta più sicurezza da ottenere prima di poter codificare il più velocemente in Scala e le sue librerie come posso con le sue librerie in Java.

Ad ogni modo, sembrava che tu volessi una storia personale da cui trarre le tue conclusioni sulla possibile redditività di un compilatore "a codice singolo ipotizzato basato su un parallelismo automatico". Speriamo che questo ci abbia aiutato.

    
risposta data 21.03.2012 - 16:10
fonte
1

Sì, ma questi problemi sono pochi e distanti nel mondo delle app line-of-business.

Il mio problema è stato risolto implementando manualmente una soluzione con thread. Avevo una posizione e molte risorse, e dovevo calcolare il tempo necessario per ogni risorsa per raggiungere la posizione. Eseguire i calcoli in parallelo era banale, ma offriva l'opportunità di ridurre il tempo complessivo impiegato da n (risorse) a 1.

Naturalmente, dato che il problema era banale da implementare (spingere ogni risorsa in una coda, che era stata scoccata da un pool di thread per calcolare con un semaforo semplice in attesa che tutte le risorse completassero), un compilatore intelligente non avrebbe ho offerto molto aiuto C'è OpenMP che offre il tipo di compilazione intelligente con solo un paio di pragma, o costrutti di programmazione funzionale che rendono questo tipo di divisione delle attività facile.

    
risposta data 21.03.2012 - 16:32
fonte
1

Is there a real-world problem that you have experienced where a "smart-enough" compiler would have provided a real benefit, i.e that someone would pay for?

In un precedente datore di lavoro, ho lavorato in un gruppo che ha scritto software per la simulazione energetica degli edifici residenziali. Fondamentalmente, ogni esecuzione di simulazione utilizza gli ultimi 20 anni di tempo (i set di dati includono misurazioni meteorologiche orarie in vari aeroporti in tutto il mondo) per un edificio nella posizione e nell'orientamento dell'edificio. Ciò consente all'utente di determinare quali cambiamenti nell'isolamento, nel riscaldamento o in altre cose farebbero la più grande esplosione per la loro particolare situazione.

Da una mia precedente domanda:

Individual tasks for offloading the simulation would be

- packaging a file (about 5Mb),
- uploading it to our servers,
- decomposing the package into individual simulations (each run takes about 30-120 seconds and is totally parallelizable), the number of simulations is a function of the number of options selected by the user (insulation, building orientation, etc) and the worst case of selecting every possible option would result in about 1E50 simulations. Running 100 to ~1E5 simulations isn't unknown, but the majority of users will run less than 10.
- reassembling the completed simulations and downloading the now much larger file.

Source
I tagli al budget sono arrivati e io non ci sono più, quindi la domanda su scicomp è discutibile.

Un architetto / ingegnere che esegue un gran numero di simulazioni per determinare l'effettivo consumo di energia per uno sviluppo abitativo (e gli schemi di isolamento / riscaldamento / raffreddamento più efficaci per case con diversi orientamenti) potrebbe facilmente passare un paio di settimane su una macchina a 8 core con tutte le varie combinazioni. Oppure, potrebbe essere parallelizzato ed essere eseguito in un paio di minuti nel 42,440 core cluster (il download dei risultati potrebbe richiedere un giorno).

    
risposta data 21.03.2012 - 17:40
fonte
1

E riguardo la transcodifica video? Questa è un'operazione molto affamata della CPU, e anche se ci sono alcuni codificatori multithread, la maggior parte sono single thread e non sono così veloci.

È un problema abbastanza grande che le persone creano e acquistano hardware costoso per farlo per la cpu.

    
risposta data 21.03.2012 - 19:21
fonte
-3

Il problema è nei più banali settori dell'informatica per i quali viene scritta la maggior parte dei programmi:

  • calcolo dell'interesse

  • aggiunta di imposte sulle vendite a una fattura

  • instradare un'e-mail

  • Mi piace un'immagine di un cucciolo ecc.

non si prestano al tipo di elaborazione parallela utilizzata per simulare un'esplosione di una bomba all'idrogeno, o, prevedendo il percorso di un uragano.

Per questi tipi di attività è necessario eseguire la logica in sequenza per ottenere il risultato corretto. È comunque possibile eseguire più attività individuali in parallelo, per massimizzare l'utilizzo dell'hardware. Questa è stata una pratica comune anche prima che le macchine SMP fossero concepite, e vi è una grande quantità di software là fuori dedicato a eseguire diverse attività in parallelo dall'antico e venerabile CICS, a Java EE e server specializzati come Apache e ASP per il web servire.

Ci sono diverse lingue che hanno caratteristiche / architetture che facilitano il multi-threading e l'esecuzione parallela che risale a PL / 1 recenti esempi degni di nota sono Erlang, Scala e Go.

    
risposta data 21.03.2012 - 02:52
fonte

Leggi altre domande sui tag