Adaptive IO Optimization problème

Question

est ici un problème d'optimisation intéressante que je pense depuis quelques jours:

Dans un système que je lis les données d'un périphérique IO lente. Je ne sais pas à l'avance combien de données j'ai besoin. La longueur exacte n'est connue qu'une fois que j'ai lu un paquet entier (pensez-y car il a une sorte de symbole de fin). Lire plus de données que nécessaire n'est pas un problème, sauf qu'il perd du temps dans IO.

Deux contraintes entrent également en jeu: Les lectures sont très lent. Chaque octet que je lis coûte. Chaque requête de lecture a également un coût d'installation constant quel que soit le nombre d'octets lus. Cela rend l'octet de lecture par octet coûteux. En règle générale, les coûts d'installation sont à peu près aussi élevés que 5 octets.

Les paquets que je lis sont généralement entre 9 et 64 octets, mais il y a des occurrences rares des paquets plus grands ou plus petits. Toute la gamme sera entre 1 à 120 octets.

Bien sûr, je connais un peu mes données: Les paquets viennent en séquences de tailles identiques. Je peux classer trois modèles ici:

Sequences de lit avec des tailles identiques:

A A A A A ... 

séquences Alternance:

A B A B A B A B ... 

et des séquences de triplets:

A B C A B C A B C ... 

Le cas particulier des triplets dégénérés existent aussi:

A A B A A B A A B ... 

(A, B et C désignent une taille d'emballage comprise entre 1 et 120 ici).

Question:

Sur la base de la taille des paquets précédents, comment puis-je prédire la taille de la prochaine demande de lecture? J'ai besoin de quelque chose qui s'adapte rapidement, qui utilise peu de mémoire (disons moins de 500 octets) et qui soit rapide d'un point de vue calculatoire.

Oh - et la pré-génération de certaines tables ne fonctionnera pas parce que la statistique des tailles de lecture peut varier beaucoup avec différents périphériques que je lis.

Des idées?

Answer 1

Vous devez lire au moins 3 paquets et au maximum 4 paquets pour identifier le modèle.

1. Lecture de 3 paquets. Si elles sont toutes de la même taille, alors le motif est AAAAAA ...
2. Si elles ne sont pas toutes de la même taille, lisez le 4ème paquet. Si 1 = 3 & 2 = 4, le motif est ABAB. Dans le cas contraire, le motif est ABCABC ...

Avec ce plan, il est probablement une bonne idée de faire une lecture spéculative de 3 tailles de paquet (quelque chose comme 3 * 64 octets à un aller simple).

Answer 2

Je ne vois pas de problème ici .. Mais d'abord, plusieurs questions:

1) Pouvez-vous lire l'entrée asyncronously (par exemple de thread séparé, routine d'interruption, etc.)?

2) Avez-vous de la mémoire libre pour un tampon?

3) Si vous avez commandé une lecture plus longue, êtes-vous capable d'obtenir le (s) premier (x) octet (s) avant que le paquet entier soit lu? Si oui (et je pense que dans la plupart des cas, il peut être implémenté), alors vous pouvez avoir un thread séparé qui les lit à la vitesse la plus élevée possible et les stocke dans un tampon, avec blocage lorsque le tampon est plein, que votre processus normal peut utiliser un getc() synchrone sur ce tampon.

EDIT: Je vois .. c'est à cause de CRC ou le chiffrement? Eh bien, vous pouvez utiliser quelques idées de compression de données:

Tenir compte d'un simple algorithme adaptatif d'ordre N pour M symboles possibles:

int freqs[M][M][M]; // [a][b][c] : occurences of outcome "c" when prev vals were "a" and "b" 
int prev[2]; // some history 

int predict(){ 
    int prediction = 0; 
    for (i = 1; i < M; i++) 
     if (freqs[prev[0]][prev[1]][i] > freqs[prev[0]][prev[1]][prediction]) 
     prediction = i; 
    return prediction; 
}; 

void add_outcome(int val){ 
    if (freqs[prev[0]][prev[1]][val]++ > DECAY_LIMIT){ 
     for (i = 0; i < M; i++) 
      freqs[prev[0]][prev[1]][i] >>= 1; 
    }; 
    pred[0] = pred[1]; 
    pred[1] = val; 
}; 

freqs doit être un tableau de l'ordre N+1, et vous devez rappelez-vous N des valeurs prévisibles. et DECAY_LIMIT doivent être ajustés en fonction des statistiques de l'entrée. Cependant, même ils peuvent être rendus adaptatifs (par exemple, s'ils produisent trop d'échecs, la limite de désintégration peut être raccourcie).

Le dernier problème serait l'alphabet. Selon le contexte, s'il existe plusieurs tailles distinctes, vous pouvez créer un mappage un-à-un avec vos symboles. Si plus, vous pouvez utiliser la quantification pour limiter le nombre de symboles. L'algorithme entier peut être écrit avec arithmétique de pointeur, de sorte que N et M ne seront pas codés en dur.

Answer 3

Depuis la lecture est si lent, je suppose que vous pouvez jeter un peu de puissance du processeur à si vous pouvez essayer de faire une supposition de combien de lire.

Ce serait essentiellement un facteur prédictif, qui aurait un modèle fondé sur des probabilités. Cela générerait un échantillon de prédictions de la taille du message à venir et du coût de chacun. Ensuite, choisissez la taille du message qui a le meilleur coût prévu.

Puis, quand vous découvrez la taille réelle du message, utilisez la règle de Bayes pour mettre à jour les probabilités de modèle, et de le faire à nouveau.

Peut-être que cela semble compliqué, mais si les probabilités sont stockées sous forme de fractions à point fixe, vous n'aurez pas à faire face à virgule flottante, il est peut-être pas beaucoup de code. J'utiliserais quelque chose comme un algorithme Metropolis-Hastings comme simulateur de base et framework de mise à jour bayésienne. (Ceci est juste une première tentative d'y penser.)