Tensorforth

Questo documento fornisce un'analisi architetturale approfondita del codice sorgente di un interprete simile a TensorForth, sviluppato per il corso di Programmazione Avanzata e Parallela del corso con lo stesso nome tenuto dal Prof. Luca Manzoni. L'obiettivo è spiegare in modo esaustivo le scelte progettuali, focalizzandosi in particolare sulle complesse dinamiche di gestione della memoria, sull'uso dello stack e sull'ottimizzazione dell'interprete.

---

1. Gestione Avanzata della Memoria (Il Core del Sistema)

La sfida principale nella manipolazione di tensori (spesso rappresentanti immagini o pesi di reti neurali) risiede nella dimensione dei dati. Copiare inutilmente vettori da centinaia di megabyte ad ogni operazione porterebbe rapidamente all'esaurimento della memoria (OOM - Out of Memory) e a prestazioni inaccettabili.

Per risolvere questo problema, TensorForth implementa un sofisticato sistema di Reference Counting a Due Livelli e sfrutta il Memory Mapping (mmap) per l'I/O.

1.1 Il Problema: Deep Copy vs Shallow Copy

In un tipico linguaggio basato su stack, operazioni come dup (duplica l'elemento in cima) o manipolazioni della forma come reshape sono molto comuni.

• Se implementassimo dup con una Deep Copy (copia profonda), per duplicare un tensore di 100MB verrebbero allocati altri 100MB di RAM e verrebbe eseguito un costoso memcpy.
• Invece, vogliamo utilizzare Shallow Copies (copie superficiali): più "entità" logiche possono condividere gli stessi dati in memoria fisica, tenendo traccia di chi li sta usando per sapere quando è sicuro cancellarli.

1.2 Reference Counting a Due Livelli (Vista vs Dati Reali)

La scelta progettuale cruciale in tensor.c e tensor.h è stata separare il concetto di "Dato" dal concetto di "Tensore".

Abbiamo due strutture distinte:

1. TensorStorage (I Dati Reali):

   • Contiene il vero array di float (float *data).
   • Possiede un proprio ref_count (quanti Tensor stanno puntando a questo storage).
   • Sa come è stata allocata la memoria (tramite malloc o mmap).

2. Tensor (La Vista/Metadati):

   • Definisce come leggere i dati: numero di dimensioni (ndim), forma (shape), totale degli elementi.
   • Possiede un puntatore al TensorStorage.
   • Possiede anch'esso un proprio ref_count (quante volte questo specifico Tensor è presente sullo stack dell'interprete).

Perché due livelli? Prendiamo l'operazione di reshape (operatore r) o ravel (operatore _): i dati sottostanti non cambiano, ma cambia la forma (es. da 100x100 a vettore di 10000). Se avessimo un solo livello, non potremmo avere due forme diverse per gli stessi dati. Avendo due livelli, reshape crea un nuovo oggetto Tensor (nuova vista, nuova forma) che punta allo stesso TensorStorage dell'originale. Il ref_count dello storage viene incrementato.

1.3 Ciclo di Vita e Garbage Collection "Manuale"

La memoria viene pulita automaticamente a cascata:

• Quando si estrae un elemento dallo stack per usarlo in una computazione e lo si scarta, si chiama tensor_unref(Tensor *t).
• Questa funzione decrementa il ref_count del Tensor. Se arriva a 0, il Tensor viene liberato dalla memoria, e chiama la funzione per decrementare il ref_count del TensorStorage associato.
• Quando il ref_count del TensorStorage arriva a 0, significa che nessun tensore (e nessuna vista) sta più usando quei dati. Solo in quel momento viene effettivamente chiamata free() (o munmap()) sull'enorme array di float.

Questo garantisce assenza di memory leak e performance massime per le manipolazioni di stack. Le operazioni d (dup) e o (over) si limitano a fare t->ref_count++ e rimettere il puntatore sullo stack (costo temporale: O(1), costo spaziale: nullo).

1.4 Ottimizzazione dell'I/O tramite mmap (Memory Mapping)

Quando si leggono file binari di grandi dimensioni (operatore {), l'uso classico di fopen + malloc + fread è inefficiente: richiede al sistema operativo di copiare i byte dal disco alla RAM del kernel, e poi dalla RAM del kernel al buffer malloc dell'applicazione.

La scelta progettuale in TensorForth è stata usare la chiamata POSIX mmap:

• mmap dice al Sistema Operativo: "Tratta questo file sul disco come se fosse già nella memoria RAM del mio programma".
• Invece di allocare RAM e copiare byte, la funzione ritorna immediatamente un puntatore.
• Quando il programma tenta di leggere i float da quel puntatore, il sistema operativo carica i blocchi necessari dal disco in RAM in modo trasparente e iper-ottimizzato (tramite il meccanismo di Paging).
• Per supportare questa logica, TensorStorage traccia se i suoi dati derivano da mmap (is_mmap = 1). In fase di garbage collection, invece di chiamare free(), chiama munmap() per chiudere la mappatura.

---

2. Architettura dello Stack e Polimorfismo

TensorForth usa una macchina a stati(iterazione per iterazione) basata su uno Stack dinamico eterogeneo (definito in stack.c e stack.h).

2.1 Gestione Dinamica e Type-Safety

In C, per avere uno stack che accetta sia Tensori che Stringhe (necessarie per i filename), l'approccio pigro sarebbe usare puntatori generici void *. Tuttavia, questo distrugge il controllo dei tipi e porta a segmentation fault disastrosi se si tenta di sommare un tensore a una stringa(mi è successo). L'approccio corretto è quello di distinguere i due direttamente su inserimento nello stack dopo averli letti. Questo per fortuna non è un problema troppo complesso in quanto leggendo un tensore ci si aspetta l'apertura è "[" mentre per il filename è ' " ' .

La decisione è stata di implementare una struttura StackItem contenente:

• Un enum StackItemType (ITEM_TENSOR, ITEM_STRING).
• Una union che può contenere un Tensor * o un char *.

Questo "polimorfismo simulato" garantisce che ogni funzione (pop_tensor, pop_string) possa validare rigorosamente cosa sta estraendo. Se un operatore si aspetta un tensore e trova una stringa, l'interprete blocca l'esecuzione e segnala l'errore senza andare in crash.

2.2 Crescita Dinamica

Lo stack è implementato come un array contiguo che parte con una INITIAL_CAPACITY di 64 elementi. Se l'utente spinge più elementi, la funzione interna stack_grow usa realloc per raddoppiare la capacità (crescita geometrica). Questo ammortizza il costo delle allocazioni, rendendo l'operazione di push in media O(1).

---

3. Parallelizzazione e Computazione (Modulo Operations)

Il modulo operations.c esegue il calcolo puro. Qui l'efficienza non è più data da "come" si muovono i puntatori, ma da "quanto velocemente" si elaborano i milioni di float all'interno dei TensorStorage.

3.1 Funzioni di Ordine Superiore (Astrazione in C)

Esistono molte operazioni binarie identiche nel loro flusso (estrai A, estrai B, controlla la forma, esegui un calcolo result[i] = A[i] OP B[i], salva e pusha). Per non ripetere centinaia di righe di codice identiche per +, -, <, =, &, ecc., è stata creata la funzione binary_elementwise.

Questa funzione accetta come parametro un puntatore a funzione (binary_op_fn). Ciò centralizza la logica di parallelizzazione e allocazione, riducendo immensamente la duplicazione del codice e i potenziali bug.

3.2 L'uso Strategico di OpenMP

TensorForth applica l'elaborazione parallela multicore tramite le direttive #pragma omp. Le scelte di parallelizzazione sono:

• Element-wise (+, -, ecc.) e Selezioni ($): Usano #pragma omp parallel for schedule(static). L'attributo static è perfetto qui perché il tempo per calcolare ogni elemento è identico. Il sistema spartisce l'array in chunk uguali per i vari core della CPU, massimizzando il throughput.
• Moltiplicazione di Matrici (@) e Convoluzione 2D (c): Vengono usati cicli annidati (es. iterando su Righe M e Colonne N). Qui è stata usata la clausola collapse(2). Questo fonde virtualmente i due cicli esterni in un unico enorme ciclo for di dimensione M*N, permettendo ad OpenMP di distribuire il lavoro in modo molto più granulare sui thread, evitando colli di bottiglia se M è piccolo ma N è grande.
• Riduzioni (op_dot, op_sum): Quando più thread devono accumulare un valore in una singola variabile sum, ci sarebbe una "race condition" (conflitto e corruzione dei dati). Per risolvere ciò, senza l'uso di lenti mutex(o semaphores), si usa la clausola reduction(+:sum). Ogni thread accumula una somma locale in un registro privato; solo alla fine tutti i valori privati vengono sommati insieme dal master thread.
• Generatore Pseudo-Casuale (?): Decisione fondamentale: questa operazione è l'unica volutamente NON parallelizzata. La funzione C standard rand() mantiene uno stato interno nascosto e non è "Thread-Safe" né "Reentrant". Chiamarla da più thread in parallelo causerebbe colli di bottiglia massicci (a causa di lock interni al SO) o corruzione dello stream generato. È stata mantenuta seriale a garanzia della correttezza.

---

4. Tokenizzazione e Dispatching (Interpreter)

Il parsing del linguaggio è mantenuto volutamente snello e sequenziale (interpreter.c). Non costruisce un Abstract Syntax Tree (AST), ma esegue immediatamente ogni token (Approccio Fetch-Decode-Execute immediato, come il linguaggio Forth originale).

• Identificazione rapida: Il parser usa il primo carattere del token per capire la tipologia:
  • Se [: entra in parse_tensor_literal. Questa funzione deve allocare la memoria "al volo" per dimensioni sconosciute, usando la stessa tecnica di raddoppio (realloc) utilizzata nello stack. Usa strtof per scorrere i float in stringa in modo sicuro.
  • Se ": estrae un nome file.
  • Altrimenti, assume sia un operatore.
• Dispatcher O(1): La dispatch_operator è uno switch gigante che mappa caratteri ASCII (+, @, r, ecc.) a puntatori di funzioni interne. Essendo un solo carattere, il compilatore C ottimizza questo switch in una Jump Table in assembly, rendendo la scelta di quale funzione eseguire un'operazione quasi istantanea. Inoltre se si volessero mai aggiungere altre operazioni basterebbe aggiungere la funzione di interesse in 'operations.c' ed aggiungere il case che lo riguarda.

---

5. Formato Binario Custom e I/O di Rete

Oltre alla normale manipolazione PGM (per la visione/debugging), il formato dei tensori (tensor.bin) su disco è imposto rigidamente (operatore }):

1. header di tipo struct on_disk_tensor.
2. Un'area di padding vuota.
3. I dati contigui in float.

La decisione di usare il padding (scostamento DISK_DATA_OFFSET obbligato a 64 bytes) è una pratica fondamentale in calcolo parallelo. Le moderne architetture hardware organizzano la memoria della CPU in "Cache Lines" grandi tipicamente 64 byte. Assicurare che l'inizio dell'array di float parta da un byte multiplo di 64 assicura l'allineamento in memoria. Quando usiamo mmap, il sistema operativo mappa il file direttamente in RAM. Grazie al padding, l'array float restituito è pre-allineato, permettendo ai registri del processore di caricare ed elaborare i dati a molto più velocemente, senza sprechi di cicli di clock necessari al riallineamento dei byte non conformi o al caricamento di chunk non allineati.

Conclusione

TensorForth dimostra come, con un attento utilizzo di tecniche C a basso livello (reference counting isolato, union typesafe, memory mapping posix, memory layout alignment, thread-safe function pointers con OpenMP), sia possibile creare un esecutore matematico estremamente compatto (meno di mille righe di codice core) ma capace di elaborare carichi di lavoro scientifici o di elaborazione delle immagini a prestazioni paragonabili a linguaggi moderni fortemente specializzati.