Complessità I/O di una classe di algoritmi di programmazione dinamica

An important class of Dynamic Programming-based algorithms, including the CYK parsing algorithm, can be modelled on the one solving the so-called “matrix chain multiplication” problem, which given a series of matrices to be multiplied finds the best parethesization, namely the one that allows to compute the result with the least possible number of scalar multiplications. This work aims at analysing the I/O complexity of a posssible implementation of the previously mentioned algorithm and solutions to minimize the number of cache misses are searched for. Specifically, an intervention on cache policies is not considered, whereas changes in the operation order and the usage of instructions to control cache and main memory content are contemplated.

Un’ importante classe di algoritmi basati sulla programmazione dinamica, fra i quali figura l’algoritmo CYK per verificare l’appartenenza di una stringa a un linguaggio context- free, può essere esemplificata da un algoritmo che individua la miglior parentesizzazione per la moltiplicazione di una catena di matrici, ovvero quella che permette il calcolo del risultato col minor numero possibile di moltiplicazioni fra scalari. In questo lavoro si analizza la complessità I/O di una possibile implementazione dell’algoritmo suddetto e si cercano strategie per minimizzare il numero di cache miss, senza però intervenire sulle politiche della cache. Nello specifico, si assume di poter modificare l’ordine delle operazioni e di disporre di istruzioni che consentano il controllo del contenuto della cache e della memoria principale.