It is available online at https://doi.org/10.36253/979-12-215-0975-5.39

Quando la teoria diventa applicazione: dalle matrici di vincoli sulle differenze allo scheduling di un sistema elettromeccanico

Enrico Vicario

Introduzione

Questo contributo riporta dello sviluppo di un algoritmo di schedulazione per un sistema elettromeccanico di analisi immunodiagnostica, nato da una collaborazione tra il Laboratorio di Tecnologie del Software1 dell’Università di Firenze e la sede produttiva di Ponte a Ema di BioMérieux Italia, negli anni attorno il 2010.

È allo stesso tempo un caso di ricerca e di trasferimento tecnologico, che in qualche misura esemplifica un tratto saliente dell’ingegneria: l’arte di costruire applicazioni su una base scientifica, dove le caratteristiche di un’applicazione a volte offrono l’occasione per un motivato sviluppo teorico e sperimentale.

Il problema: scheduling di attuatori condivisi nell’esecuzione concorrente di molteplici analisi immunoenzimatiche

Un’ampia classe di protocolli di analisi immunenzimatica procede trasformando un campione attraverso il contatto con una sequenza di reagenti biologici, fino a produrre un risultato la cui apparenza visiva rivela la quantità di interesse. È qui particolarmente rilevante che ciascuna reazione ha una durata vincolata tra un minimo e un massimo prescritti dal protocollo.

Nella pratica dei laboratori diagnostici, il protocollo è automatizzato attraverso un sistema elettromeccanico dove (Figura 86): i reagenti sono contenuti nelle provette (tubes) di un blister; il campione viene trasferito da una provetta alla successiva attraverso aspirazioni e iniezioni attuate da un pipettatore movimentato da un motore elettrico e collegato ad una pompa; e il campione finale viene classificato attraverso una testa di lettura ottica.

L’ applicabilità pratica e la competitività industriale di un tale sistema, dipendono in modo cruciale dalla capacità di eseguire in parallelo un elevato numero di analisi, condividendo un unico pipetattore ed una unica testa di lettura, e i molti componenti che stanno dietro di loro.

Figura 86 – Un pipettatore e una testa di lettura vengono condivisi nell’esecuzione di più analisi biologiche, ciascuna realizzata sulla sequenza di provette di un blister.

Il problema si trasferisce a questo punto dal livello elettro-meccanico a quello informatico, nella forma di un problema di scheduling: per ciascuna delle analisi eseguite in parallelo, occorre individuare tempo di avvio e tempi di trasferimento fra le celle del blister, in modo tale che tutti i trasferimenti possano essere operati condividendo nel tempo l’uso di un unico pipettatore, nel rispetto dei vincoli di minimo e massimo della durata del soggiorno di ciascun campione in ciascuna cella di reazione. Va da sé che questo sottende un vincolo di mutua esclusione, perché il pipettatore non può essere su due analisi diverse allo stesso tempo (Figura 87).

Figura 87 – I vincoli sul tempo di contatto con ciascun reagente identificano un sistema di disequazioni sulle differenze fra i tempi ai quali il pipettatore deve servire il trasferimento fra provette di ciascun blister (qui esemplificato per il caso semplificato di 3 blister con due reagenti ciascuno). Il vincolo di mutua esclusione nell’uso del pipetattore identifica una molteplicità di modi con cui è possibile ordinare le attuazioni (qui esemplificato in due soluzioni, in arancione e in marrone).

Il requisito funzionale è accompagnato da vincoli strutturali: il problema deve potere essere risolto per 32-64 analisi biologiche in parallelo, per protocolli biologici fino a qualche decina di reazioni, anche eterogenei, utilizzando una unità di calcolo costruita su un processore industriale di basso costo, con severe limitazioni di memoria e capacità computazionale (10-20 volte più lento di un processore di consumo, con soli 32Mbytes di memoria, di cui al più 6 dedicati allo scheduler), tale da potere essere ospitata a bordo del sistema elettromeccanico. E ci sono infine vincoli di qualità2, in particolare circa le prestazioni, che in ultimo diventano vincoli di adeguatezza funzionale: tutto questo deve avvenire entro una mezza dozzina di secondi, intesi come limite ergonomico sul tempo che il biologo può pazientare fra il momento in cui ha caricato la macchina e quello in cui riceve il riscontro del suo corretto avvio.

Complessivamente, tutto questo costituisce un nitido caso di esempio del concetto di Cyber-Physical System: un sistema fatto di componenti che rispondono a leggi fisiche, governati da algoritmi implementati in software. È questo uno dei paradigmi di riferimento della ricerca di questi decenni, dove convergono le competenze che sono state connesse nella costituzione del Dipartimento di Ingegneria dell’Informazione3: Elettronica, Elettromagnetismo, Telecomunicazioni e Reti di Comunicazione, Misure e Sistemi Elettrici, Automazione e Robotica, Biomedicina, Ottimizzazione, Informatica, Visione Computazionale, Software e Intelligenza Artificiale. Nell’interpretare il termine, può interessare notare che il termine Cyber deriva dal greco antico Kubernetes, il timoniere che guida una nave, e dallo stesso etimo deriva poi il termine governo.

Gli ingredienti della soluzione sviluppata: Difference Bounds Matrices, mantenute in forma normale in una ricerca A* attraverso Floyd Warshall shortest-path

Non conviene entare qui nei dettagli tecnici, che sono parzialmente riportati in un articolo di letteratura scientifica (Ridi, Torrini, Vicario 2011), ma ne delineiamo gli ingredienti fondamentali.

L’elemento centrale è l’algebra delle difference-bound matrices (DBMs) (Dill 1989), sistemi di disequazioni lineari sulle differenze fra una collezione di variabili. In questo caso le variabili sono i tempi di iniezione nelle celle dei blister in analisi biologica, e le disequazioni formalizzano i vincoli sul tempo di incubazione che il protocollo prescrive per ciascuna reazione.

I metodi di rappresentazione e manipolazione computazionalmente efficiente di DBMs si sono sostanzialmente consolidati negli anni ’90, anche con il contributo di questo autore che all’epoca ci lavorava come elemento centrale per la sua tesi di dottorato poi parzialmente riportata in (Bucci, Vicario 2002; Vicario 2002). La fortuna di questa struttura dati deriva dalla capacità di rappresentare in modo inerentemente valido il comportamento di un sistema di componenti con timers che avanzano con la stessa velocità, e la sua applicabilità pratica discende dal fatto di poterla rappresentare e manipolare entro limiti di complessità computazionale e di memoria di ordine cubico o quadratico rispetto la numero delle durate soggette a vincoli. Un dettaglio che ha qui qualche rilevanza è l’esistenza di una forma normale di rappresentazione che può essere calcolata in tempo cubico attraverso l’algoritmo all-shortes-path di Floyd Warshall, con la possibilità di ridurre il tempo all’ordine quadratico quando la normalizzazione è eseguita a caldo dopo una perturbazione parziale dei vincoli (Vicario 2002).

Le DBM costituiscono oggi la base per un’ampia varietà di strumenti ampiamente documentati nella letteratura scientifica, quali Uppaal (Bengtsson et al. 1996), Kronos, Romeo, Tina, Oris (Paolieri et al. 2021), finalizzati alla modellazione, la verifica di correttezza e la valutazione di affidabilità e prestazioni di sistemi concorrenti con durate incerte soggetti a vincoli di tempo reale.

Altro ingrediente significativo, sono un paio di algoritmi classici, spesso ricompresi nel bagaglio culturale di un ingegnere informatico: l’algoritmo di ricerca A* qui usato per avere una euristica efficiente nell’esplorazione dei possibili ordinamenti con cui risolvere il vincolo di mutua esclusione nell’uso del pipettatore sulle diverse analisi; e l’algoritmo all-shortest-path di Floyd Warshall, qui utilizzato per mantenere in una forma canonica i vincoli delle DBM generate nel corso dell’esplorazione.

L’ultimo ingrediente, il software con cui tutta questa teoria di algoritmi è implementata, sviluppato prima in Java a partire da una codebase già disponibile in Laboratorio e poi riportato in c per ragioni di efficienza e riduzione delle dipendenze, cruciale per mettere a punto e valutare l’impatto di un numero di ottimizzazioni algoritmiche emerse nel corso dello sviluppo.

Risultati e conclusioni

All’avvio del progetto il requisito strutturale di potere calcolare lo schedule su un processore industriale a bordo del sistema elettromeccanico appariva incompatibile con il requisito prestazionale di completare il calcolo entro qualche secondo. Questo anche nel giudizio raccolto nell’ambito industriale di scala internazionale in cui era collocata la collaborazione. E questo in effetti sarebbe stato l’esito se l’ottimizzazione fosse stata realizzata con metodi convenzionali che non facessero leva sulla specializzazione abilitata dal particolare caso.

Fino dalle prime misure raccolte sulla versione del software ancora in sviluppo apparve invece possibile completare il calcolo entro tempi nell’ordine delle centinaia o decine di millisecondi, con una diretta corrispondenza tra misure e previsione teorica della complessità (Ridi, Torrini, Vicario 2011).

La rilevanza del risultato e la sua importanza per lo sviluppo del sistema elettromeccanico in cui è integrato motivarono un brevetto, depositato in Europa, negli Stati Uniti e su scala mondiale, ancora oggi mantenuto da BioMeérieux, per un sistema elettromeccanico che è leader mondiale nel suo ambito e che viene ancora oggi sviluppato e prodotto presso la sede di Ponte a Ema.

Per il Laboratorio di tecnologie del Software, quell’esperienza valse un articolo su una rivista di culto per un softwarista (Ridi, Torrini, Vicario 2011), il riconoscimento di invenzione su un brevetto internazionale per un componente di un sistema in uso (Vicario et al. 2013), e un finanziamento di un certo rilievo per ulteriore ricerca attorno al tool Oris (Paolieri et al. 2021), ancora oggi oggetto e strumento di ricerca scientifica presso il Laboratorio di Tecnologie del SW.

Riflettendoci a posteriori, questo appare come un caso molto fortunato. Di norma, la ricerca scientifica si focalizza su temi di elevata specializzazione, che coprono punti specifici lungo la frontiera della conoscenza e che raggiungono un impatto tangibile attraverso la condivisione su scala internazionale. E invece qui, in modo molto accidentale, avvenne che uno specifico tema di ricerca sviluppato presso un Laboratorio dell’Università di Firenze si potesse attagliare allo sviluppo di una soluzione su misura per un problema che poteva trovare impatto applicativo nella capacità industriale dello stesso territorio.

Riferimenti bibliografici

Bengtsson, J. et al. 1996. “UPPAAL — a tool suite for automatic verification of real-time systems.” Workshop on Verification and Control of Hybrid Systems III. Springer.

Bucci, G. e E. Vicario. 2025. Computer Technology in 100 cards. McGrawHill.

Dill, D. 1989. “Timing assumptions and verification of finite-state concurrent systems.” International Conference on Computer Aided Verification (CAV). Springer.

Paolieri, M., M. Biagi, L. Carnevali e E. Vicario. 2021. “The ORIS tool: quantitative evaluation of non-Markovian systems.” IEEE Transactions on Software Engineering 47: 1211-25.

Ridi, L., J. Torrini e E. Vicario. 2011. “Developing a scheduler with difference-bound matrices and the Floyd-Warshall algorithm.” IEEE Software 29: 76-83.

Vicario, E. 2002. “Static analysis and dynamic steering of time-dependent systems.” IEEE Transactions on Software Engineering 21: 728-48.

Vicario, E., L. Ridi, J. Torrini e A. Carignano. 2013. Job scheduler for electromechanical system for biological analysis. Brevetto WO 2013098088 A1, EP20110196275.

Enrico Vicario, University of Florence, Italy, enrico.vicario@unifi.it, 0000-0002-4983-4386

Referee List (DOI 10.36253/fup_referee_list)

FUP Best Practice in Scholarly Publishing (DOI 10.36253/fup_best_practice)

Enrico Vicario, Quando la teoria diventa applicazione: dalle matrici di vincoli sulle differenze allo scheduling di un sistema elettromeccanico, © Author(s), CC BY 4.0, DOI 10.36253/979-12-215-0975-5.39, in Stefano Selleri, Alberto Tesi, Enrico Vicario (edited by), Ingegneria Industriale & Ingegneria dell’Informazione per il territorio fiorentino – 2. Ingegneria dell’Informazione, pp. -163, 2026, published by Firenze University Press, ISBN 979-12-215-0975-5, DOI 10.36253/979-12-215-0975-5