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)
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
- un numero finito di piedi (porte) per ricevere segnali dai sensori dell'oggetto di controllo (ogni segnale è un binario),
- 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
- 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 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
(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 
, e se assumiamo che il tempo di permanenza di una partizione è 1 millisecondo, poi per la costruzione di tutte le partizioni necessarie risulterà 
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:
- Il numero di blocchi della 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. - Il grado di sovrapposizione delle condizioni logiche
- Il grado di 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). - La complessità dei collegamenti di interconnessione di rete
. 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)L'intensità delle interazioni di 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 
, 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à 
il multi-criterio del problema si riduce ad una sola condizione:
- 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.
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".
Assemblaggio delle celle di motori elettrici
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 
e la probabilità di ottenere i criteri minimi di qualità per la selezione di 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.
e allo "Stato del server" 
. nella scheda qui sotto.
Supporto al progetto: supportato
.
| Join al Team | |
| Applicazioni | |
| Stato del server | |
|
Statistiche interne del progetto |
 |
|
Classifica interna utenti |
 |
|
Pagina dei risultati |
 |
|
Statistica del Team sul progetto |
 |
| Classifica dei team italiani |  |
| Statistiche del Team |  |
| Classifica Utenti | |
| Classifica mondiale del Team |
|
