Valutazione attuale: 5 / 5

Stella attivaStella attivaStella attivaStella attivaStella attiva
 
banner gerasim

 

AMBITO: Matematica
STATO:  ATTIVO 
ATTACH: http://gerasim.boinc.ru/

 

Aree di ricerca
Trasformazioni equivalenti e partizionamenti di schemi-grafi di algoritmi di controllo di logica parallela per il design di sistemi di controllo logici.

Obiettivo scientifico
Analisi della qualità delle partizioni schemi-grafi di algoritmi di controllo di logica parallela, ottenuti con diversi metodi euristici.

Descrizione del progetto
I sistemi di controllo logico (PLC) recentemente sono diventati più diffusi a causa del crescente utilizzo di linee di assemblaggio robotizzate automatiche in grado di effettuare le operazioni necessarie con poco o nessun intervento umano (o riducendo tale coinvolgimento al minimo), da un lato, e il successo della microelettronica (FPGA, GA, SOC, ecc), che segue la legge di Moore, dall'altro.

 

Le applicazioni di questi sistemi sono:

  • La gestione dei componenti critici all'interno di un ambiente in cui un errore, causato da un intervento umano (o da altre cause), può portare a gravi conseguenze di natura tecnologica, sociale o economica (gestione delle centrali nucleari, missili, satelliti, ecc.). Per i sistemi di questa classe con requisiti ad alte prestazioni, con tolleranza ai guasti e, se possibile, implementando un complessità hardware a basso costo (a causa dei suoi effetti sul peso e parametri di dimensione).
  • La gestione di dispositivi elettronici (processori, acceleratori, calcolatrici specializzate, ecc), la cui frequenza può essere fino a diversi gigahertz. In questa luce, come nei sistemi di controllo, al primo posto ci sono i requisiti ad alte prestazioni e a basso costo, in parte dovuti all moderata complessità dell'hardware.
  • Gestione linee di trasporto robotizzate o macchine con CNC, che riducono sostanzialmente la gestione degli attuatori inerziali e non richiedono elevate prestazioni: ribalta i criteri di basso costo e la possibilità di una rapida introduzione di PLC come gestori delle operazioni (introduzione di nuove apparecchiature, cambiamenti nella composizione prodotti, ecc)
 
Per ulteriori informazioni visitate il thread ufficiale presente nel nostro forum.

banner gerasim

 

Tra i tanti approcci alla costruzione di tali sistemi di gestione la base del nostro approccio è incentrata sull'uso di logiche Multi-Moduli. Logica Multi-Controller è un insieme dello stesso tipo di controllori logici programmabili, co-gestite da un oggetto (attuatore, dispositivo elettronico, ecc). Questa classe di dispositivi combina i principi di uniformità, la modularità, la tolleranza ai guasti, le alte prestazioni, la complessità hardware moderata e i costi contenuti. Le caratteristiche del controller (di solito eseguito come chip) sono limitati: ha

  1. un numero finito di piedi (porte) per ricevere segnali dai sensori dell'oggetto di controllo (ogni segnale è un binario),
  2. un numero finito di porte per l'uscita dei segnali delle azioni di controllo (le cosiddette micro-operazioni, che sono anche segnali binari) in materia di gestione e
  3. capacità di memoria limitata del firmware.

Al fine di semplificare la struttura interna del regolatore è generalmente (ma non sempre) permesso di presentare il firmware come parte di rami paralleli (nello stesso modo sono organizzati i moderni processori – il programma assembly è coerente ed eseguito da un singolo processore: per l'esecuzione parallela sul processore multi-core, un cluster o supercomputer l’algoritmo parallelo complesso è diviso in “frammenti successivi”, ciascuno dei quali viene eseguito su di un singolo processore). Nell'attuare l’algoritmo di controllo complesso (diverse centinaia di segnali provenienti dai sensori, le azioni di controllo di diverse centinaia, migliaia di vertici costituiti dai grafi di controllo), disporre di un unico controller potrebbe essere insufficiente, quindi è necessario che siano combinati in un multi-controllore logico.

 sistema controller unico

Sistema a controller unico

I Multi-Moduli moderni possono contenere diversi controller, ad esempio, incorporati nel ring, a matrici di ipercubi (matrici di processori divisi in piani orizzontali e verticali) e gruppi di decine di migliaia di controllori. Il disegno SLN basato su tale multicontroller non è banale e richiede la soluzione di un certo numero di sotto-compiti:

  • Partizione - presentazione del grafo originale di una pluralità di blocchi, ciascuno dei quali soddisfa la tecnologia (può essere fatta senza violare le limitazioni del regolatore del numero di segnali di ingresso/uscita e la capacità di memoria) e funzionali (non comprende picchi paralleli) costituito limitazioni controllori PLC .
  • Alloggio - Selezione della partizione appropriata tra le unità e controllori (che bloccano la fonte dell'algoritmo parallelo).
  • Resilienza - garantendo efficienza in presenza di un numero di controllori inefficienti (ad esempio, se in un sistema di 10.000 controllori sono inoperabili più controllori, il sistema deve continuare ad operare, con eventualmente una efficienza leggermente minore).
  • Routing - fornendo capacità di scambio dati failover tra qualsiasi controllore del sistema (compreso l’oggetto di guasti che possono verificarsi durante il funzionamento).
  • eccetera
Attualmente, il progetto Gerasim@home analizza dei metodi per risolvere il primo problema. (in futuro, potranno essere aggiunti nuovi moduli di calcolo per le altre attività). Ciascuno di questi problemi può essere risolto in diversi modi, e il numero di possibili soluzioni è di solito un numero di astronomico. Ad esempio, il numero di partizioni di un dato schema grafico di blocchi non superi i numeri di Bell  numeri di bell 

(in realtà diverse volte di meno, a causa del fatto che non tutte le possibili partizioni sono corrette, ovvero soddisfano i vincoli).
Ad esempio, ponendo n=20, allora bell 20 , e se assumiamo che il tempo di permanenza di una partizione è 1 millisecondo, poi per la costruzione di tutte le partizioni necessarie risulterà risultato bell 20 anni di tempo di calcolo. Quando n=100, la quantità di tempo di elaborazione richiesto sarà di circa 100 milioni di anni.

Alcuni algoritmi di controllo reale flow-chart possono contenere fino a diverse migliaia di vertici. La costruzione dell'insieme di tutte le decisioni prese al fine di selezionare i migliori (e la soluzione trovata) è chiamato ottimalità (o riduzione ottimale).
I compiti per i quali è impossibile ottenere una soluzione ottimale in un tempo ragionevole sono chiamati “intrattabili” o NP-completo (il problema di scegliere il partizionamento ottimale si riferisce a questa classe). Per risolverli non si usano, in pratica, metodi di ricerca esaustiva di tutte le soluzioni, ma ci si limita a considerare solo parti (metodi iterativi) o la sintesi una soluzione "buona" (modalità omogenee), che di solito è peggiore della ottimale per non più dell’ 1-2% (utilizzando un buon metodo). Le soluzioni ricavate usando euristiche simili sono chiamate non ottimali.

Ci sono varie soluzioni da confrontare l’un l'altra, tant’è che quando si imposta un problema di ottimizzazione si introduce il concetto di criterio di qualità. Questo criterio può servire come valore minimo, come lunghezza minima delle connessioni o rotte, come massima probabilità di recapito dei messaggi, etc. Per il problema dell’algoritmo di partizionamento si usano diversi criteri simili tra loro, ma il compito stesso è un multi-criterio:

  1. Il numero di blocchi della partizione numero blocchi partizione Il criterio più importante riguarda indirettamente tutti gli altri criteri: determina, infatti, il numero di controllori del sistema di controllo (in altre parole, la sua complessità hardware) può essere inferiore al grado di parallelismo del grafo di controllo.
  2. Il grado di sovrapposizione delle condizioni logiche grado sovrapposizioni logiche
  3. Il grado di micro-duplicazione grado micro duplicazione In combinazione con la qualità delle misure precedenti valuta l’eccessivo numero di tracce sul PCB necessarie per collegare i perni ai controllori (in altre parole, l'effetto sulla complessità e il costo di produzione dei PCL).
  4. La complessità dei collegamenti di interconnessione di rete collegamenti interconnessione. Specifica il numero di micro-op di trasferimento del comando tra i controllori del sistema: influenza la profondità delle linee di campo e il valore word di comando bit (in altre parole, la complessità dell'hardware del controller).
  5. 5)L'intensità delle interazioni di interconnessione interazioni interconnessione. Determina il numero medio di trasmissioni tra controllori di gestione per l'esecuzione dell'algoritmo di controllo (del traffico) influisce sulle prestazioni. Vi possono essere casi in cui, a fronte di molteplici soluzioni, è difficile scegliere univocamente il migliore. Per fare ciò, il valore numerico di ciascun criterio è normalizzata (data una serie serie, moltiplicato per un fattore di ponderazione (i valori dei coefficienti sono scelti dagli esperti), i valori ottenuti vengono aggiunti per formare un indicatore integrante della qualità j il multi-criterio del problema si riduce ad una sola condizione:
     multi criterio 1
    multi criterio 2
Il partizionamento dello stesso algoritmo di controllo può essere ottenuta con vari metodi:
  • Metodo “S.I. Baranova” (implementazione software di Vatutin, numero di registrazione 2010612902) - un classico esempio di algoritmo Greedy. Metodo sequenziale, costruisce una partizione incorporando i nodi più idonei nel primo blocco mentre è possibile, poi il secondo, ecc fino a quando saranno considerati tutti i nodi. Ottimizzato solo per una parte dei criteri di qualità.
  • Metodo “A.D. Zakrevskogo” (implementazione software di S.V. Volobueva, numero di registrazione 2006613146) - metodo sequenziale, riduce la soluzione al problema del partizionamento a colorare un grafico speciale. Ottimizzato solo per il numero di blocchi (il numero cromatico di un grafico in un linguaggio speciale chiamato PRALU), il metodo ha alcune limitazioni tecnologiche, che sono il suo svantaggio significativo.
  •  Il metodo della decomposizione seriale-parallela (implementazione software di EI Vatutin, numero di registrazione 2005613091) - un metodo coerente, sviluppato presso il Dipartimento di Ingegneria Informatica, Kursk State Technical University. Esegue una serie di pre-trasformazioni grafo-schematiche dell'algoritmo (cicli di interruzione, combinazioni di segmenti lineari, la costruzione della matrice dei rapporti, la costruzione di una pluralità di sezioni dell'algoritmo, la realizzazione della sintesi di scheletro partizionamento del grafo), ottimizza tutti i criteri di qualità.
  • Un certo numero di altri metodi (ricerca esaustiva, ricerca esaustiva limitata, ricerca casuale) e la modifica dei metodi di cui sopra.
schematici trasformazioni preliminari 1
schematici trasformazioni preliminari 2
schematici trasformazioni preliminari 3
schematici trasformazioni preliminari 4
 
Simboli schematici di trasformazioni preliminari di grafi di algoritmi

Implementazioni software di metodi notevolmente ottimizzati a livello algoritmico sono realizzate in linguaggio assembly, ottimizzato per l'uso con il vettore di set di istruzioni processore MMX e SSE (numero di registrazione 2007614221). Per un confronto obiettivo dei metodi necessari per condurre una serie di esperimenti computazionali, si studiano metodi particolari in condizioni diverse (algoritmo di controllo ridimensionamento differente per differenti valori di limitazioni, per diversi valori dei parametri e diversa composizione delle trasformazioni). Lo scopo di questo progetto è di condurre un confronto più dettagliato della qualità delle decisioni dei vari metodi (che richiede più potenza di elaborazione). La costruzione di un numero maggiore di partizioni permette di dare una più accurata grafica "liscia" (riducendo l’intervallo di confidenza). Negli esperimenti computazionali sono previsti dei metodi per un confronto più approfondito (passaggio da un parametro per lo schema a due parametri).
In definitiva, questo creerà un sistema di controllo logico più efficace con meno complessità dell'hardware, minori costi di produzione e una maggiore velocità. Inoltre, un algoritmo di conversione grafo-schematico di algoritmi possono essere utilizzati in compiti di calcolo parallelo, ottimizzando programmi moderni compilatori ottimizzanti, oltre a risolvere diversi problemi nella teoria dei grafi. Il lavoro su questi argomenti è stato pubblicato più di 40 lavori scientifici: i risultati degli studi sono stati utilizzati per lo sviluppo di un canale di comunicazione digitale per le valvole di isolamento del sistema di controllo, quando si progetta la logica di controllo del sistema di robot per l'assemblaggio di bassa potenza motori elettrici DC attuale, il progetto del sistema di controllo della caldaia "Caldaia-M2M".

celle motori elettrici

Assemblaggio delle celle di motori elettrici

partizione algoritmo controllo 1

partizione algoritmo controllo 2

 Partizione dell’algoritmo di controllo e relativa rappresentazione schematica (dopo l’assegnazione di criteri di qualità)

Al ricevimento del lavoro di calcolo (Working Units, WUs) nel computer su cui è presente il gestore BOINC, viene avviata la costruzione delle partizione algoritmi di controllo di un determinato volume di campione e la dimensione dei valori delle limitazioni tecnologiche, le stime dei risultati (criteri di qualità) sono indicate e il risultato è inviato al server. Per ciascun criterio di qualità essa viene calcolata sulla coppia di valori: il valore medio del criterio di qualità per la selezione di algoritmi di dimensione specificata tra le partizioni, ottenuto con il metodo scelto metodo scelto e la probabilità di ottenere i criteri minimi di qualità per la selezione di algoritmi specificati algoritmi specificati. Il valore medio dei criteri dovrebbe essere il più piccolo possibile, mentre la probabilità massima. I valori ottenuti sono visualizzati in un diagramma a due parametri e vengono utilizzati per confrontare i metodi per costruire le partizioni, per valutare l'impatto delle varie modifiche, etc.


banner gerasim




Stato del progetto: progetto attivo
Iscrizione libera.

 

Requisiti minimi: nessuno
Gli sviluppatori non segnalano requisiti minimi da rispettare.

 

Screensaver: disponibile non disponibile
Note o immagine

 

Assegnazione crediti: fissati per singola WU/ variabili in base al tempo di elaborazione
Quorum = 2 (se è >1 le WU dovranno essere convalidate confrontando i risultati con quelli di altri utenti).

 

Applicazioni e WU disponibili:
Cliccare sulle icone relative alle "Applicazioni" ico32_applicazioni e allo "Stato del server" ico32_server. nella scheda qui sotto.

 

Sistemi operativi supportati:

 

Dati specifici sull'elaborazione:
Per ottenere dati sulla durata media dell'elaborazione, la RAM necessaria e la dead line, consultare la scheda "Info tecniche" qui a destra. Per informazioni particolareggiate (specifiche per applicazione e sistema operativo, intervallo di backup e crediti assegnati) rifarsi alla pagina dei risultati del progetto WUprop@home.

 

Problemi comuni: nessuno vedi elenco
Non si riscontrano problemi significativi.

 

 Supporto al progetto: supportato

Per unirsi al team BOINC.Italy consultare la scheda "Link" qui sotto cliccando sull'icona relativa al "JOIN" ico32_bi.

 

Referente/i: posizione vacante
Se sei interessato al progetto e vuoi dare una mano diventando referente, contatta i moderatori in privato o attraverso le pagine del forum.

banner gerasim

 

 

 
Link utili
Join al Team ico32_bi
Applicazioni ico32_applicazioni
Stato del server ico32_server

Statistiche interne

del progetto

ico32_stats

Classifica interna utenti

ico32_classutenti

Pagina dei

risultati

Pagina dei risultati
 
 
 
Statistiche BOINC.Stats

Statistica del Team sul

progetto

ico32_boincstats
Classifica dei team italiani ico32_statita
Statistiche del Team Team Stats
Classifica Utenti ico32_classutenti
Classifica mondiale del Team

ico32_stats

 
 
Posizione del team nelle classifiche modiali:




Per commentare questo post nel forum devi effettuare il login