[C/C++] struttura dati da usare

[misterx]

devo controllare un certo numero di segnali provenienti da alcuni apparati. Ogni apparato può generare da 1 a più segnali ed ogni apparato deve avere un nome.

Ogni apparato ha un range di 128 byte dei quali alcuni vengono usati mentre altri potrebbero non venire affatto usati.

Ho ad esempio l'apparato A con 127 byte(segnali), l'apparato B con 127 byte(segnali) e così via sino ad H e anche più.

Usare un array per ogni apparato non mi pare una gran soluzione o forse lo è, usare n alberi binari non so se abbia senso; il fatto è che devo dinamicamente continuare a verificare il loro stato: qualche idea?

grazie

[WarDuck]

Anche se tu avessi 1000 apparati da 128byte l'uno, staresti a 128000 bytes ovvero circa 128Kbytes...

Con le cache attuali potrebbero stare tutti all'interno della cache del processore.

Tutto dipende da dove devi fare girare il programma e se hai dei requisiti prestazionali in termini di occupazione di memoria .

Gli array godono dell'accesso diretto che non è cosa da poco.

[misterx]

già, hai ragione
Deve girare su un PC di ultima generazione e tenere sotto controllo in tempo reale lo stato di tutti quei byte.

Effettivamente non avendo una crescita di alcun tipo una struttura ad albero è sprecata

Mi chiedevo però: tali segnali viaggano su rete ethernet da 100 Mbit e possono cambiare ogni 8 ms (millisecondi) l'uno.
8 ms sono il tempo minimo sotto al quale non possono andare.

leggo da ethernet
128 byte * 10 apparati = 1280 byte = 1280*8=10240 bit

di ogni bit devo monitorare variazione e tempo di variazione ovviamente in ms, ce la faccio?

[WarDuck]

Come le calcoli le differenze? Io direi che potresti usare la funzione XOR per lavorare sui bit .

Ad esempio:

val|  bits
11 | 01011 XOR
15 | 01111 =
-----------
 4 | 00100

Se il risultato dello XOR è 0 significa che non è cambiato nulla.

Quindi se è 1 vai a leggere i bits del risultato per capire quali sono cambiati .

Io penso che tu ce la possa fare così .

[misterx]

oggi ho scoperto che 8 ms sono il massimo, in realtà si parla di nanosecondi.
Ho quindi una decina di array da 128 byte per i quali devo verificare la variazione, il tempo di variazione in nanosecondi e confrontare a gruppi tali array con altri prelevati in uno storico.

A[128]
.........
Z[128]

verifico con la XOR il cambiamento del bit, memorizzo il tempo di variazione di stato e verifico se i tempi di cambiamento sono compresi in un certo range con quelli dello storico e questo per 1280 volte almeno ogni secondo....se riuscissi ogni 1/1000 di secondo sarebbe meglio

[WarDuck]

Fai una prova e vediamo come va .

[misterx]

una ulteriore complicazione

ogni bit di ogni byte dell'array corrispondono a qualchesegnale però un certo numero di segnali rappresentano il funzionamento di un dispositivo.

I segnali di uno stesso dispositivo ha i suoi bit sparpagliati nei vari array da 128 bit, come risolvo?

char A[128];
char B[128];
................
char Z[128];

dispositivo_1=bit_1(A[5]) + bit_2(D[43]) + bit_3(H[98]) + ..... + bit_m(L[n])
dispositivo_2=bit_1(X[15]) + bit_2(W[143]) + bit_3(P[198]) + ..... + bit_m(E[n])

i dispositivi possono essere anche 1000

[!fazz]

8 ms max su ethernet e con un sistema operativo comune sono impossibili da ottenere ti serve un sistema di acquisizione con i controattributi su cui giri un sistema operativo realtime cosa che con windows e acquisizione diretta con un protocollo non deterministico sui tempi come il tcp-ip è praticamente impossibile

l'unica soluzione che mi viene in mente è usare un pxi o una crio e anche con questi con Gbit tra il controller e l'host dubito che riesci ad andare a quelle velocità che richiedi.

comunque fatto questo te la devi vedere come vengono passati i valori dall'hw di acquisizione prima di decidere che struttura dati usare per l'immagazzinamento ma visto le performance che ti servono io opeterei se possibile per una shared memory tra i dispositivi (se disponibile) ed accesso diretto alla memoria

[WarDuck]

Originariamente inviato da !fazz

8 ms max su ethernet e con un sistema operativo comune sono impossibili da ottenere ti serve un sistema di acquisizione con i controattributi su cui giri un sistema operativo realtime cosa che con windows e acquisizione diretta con un protocollo non deterministico sui tempi come il tcp-ip è praticamente impossibile

l'unica soluzione che mi viene in mente è usare un pxi o una crio e anche con questi con Gbit tra il controller e l'host dubito che riesci ad andare a quelle velocità che richiedi.

comunque fatto questo te la devi vedere come vengono passati i valori dall'hw di acquisizione prima di decidere che struttura dati usare per l'immagazzinamento ma visto le performance che ti servono io opeterei se possibile per una shared memory tra i dispositivi (se disponibile) ed accesso diretto alla memoria

In effetti con su troppa carne al fuoco comincia a diventare "pesante" ("ma avete problemi di gravità lì?" Cit.).

Programmarlo in kernel mode potrebbe migliorare le cose?

[!fazz]

Originariamente inviato da WarDuck

In effetti con su troppa carne al fuoco comincia a diventare "pesante" ("ma avete problemi di gravità lì?" Cit.).

Programmarlo in kernel mode potrebbe migliorare le cose?

no,

è proprio questione principalmente di sistema operativo e di protocolli di comunicazione, è impossibile ottenere con le macchine tradizionali il real time, e per acquisire come vuoi tu è parecchio difficile devi usare sistemi hw dedicati real time per l'acquisizione che dopo inviino i dati al pc

in alternativa potresti provare ad usare rtai e vedere fino a quanto riesci a tirare il sistema ma non lo conosco per nulla

[misterx]

oggi ho fatto delle prove "reali" e catturando 128 byte il tempo speso è circa 200 ms, molto ben lontano dagli 8 ms preventivati.

Incuriosito sono andato su un PC molto più performante ma ho ottenuto il medesimo risultato.

Appesantendo il programma con qualche conversione da intero a binario con un semplice ciclo i tempi non peggiorano di granchè, significa che il collo di bottiglia sta in rete o più precisamente nel protocollo stesso.

Facendo una simulazione in locale il tempo impiegato per generare in modo casuale e trasformare i 128 byte è quasi non misurabile.

Qualcuno ha parlato di kernel mode, signmifica che è possibile by passare lo schedulatore di windows?

[marco.r]

Originariamente inviato da misterx

oggi ho fatto delle prove "reali" e catturando 128 byte il tempo speso è circa 200 ms, molto ben lontano dagli 8 ms preventivati.

Incuriosito sono andato su un PC molto più performante ma ho ottenuto il medesimo risultato.

Appesantendo il programma con qualche conversione da intero a binario con un semplice ciclo i tempi non peggiorano di granchè, significa che il collo di bottiglia sta in rete o più precisamente nel protocollo stesso.

Probabile. Ci sono diversi fattori da tenere in considerazione: che protocollo usi per la comunicazione TCP, UDP, altro ? La rete e' dedicata (meglio ancora un cavo cross) oppure ci sono altre macchine sulla stessa ? Lavorando un po' su questi aspetti si possono migliorare le cose...

Poi, come fai a misurare la latenza ? Il pacchetto ha un suo timestamp ? I due clock sono sincronizzati ? Hai provato a misurare il tempo da quando "raccogli" il pacchetto a quando hai finito di elaborarlo ?

Qualcuno ha parlato di kernel mode, signmifica che è possibile by passare lo schedulatore di windows?

La latenza introdotta dal lavorare in userspace non dovrebbe essere cosi' rilevante, perlomeno non nell'ordine dei centinaia di millisecondi

[!fazz]

Originariamente inviato da misterx

oggi ho fatto delle prove "reali" e catturando 128 byte il tempo speso è circa 200 ms, molto ben lontano dagli 8 ms preventivati.

Incuriosito sono andato su un PC molto più performante ma ho ottenuto il medesimo risultato.

Appesantendo il programma con qualche conversione da intero a binario con un semplice ciclo i tempi non peggiorano di granchè, significa che il collo di bottiglia sta in rete o più precisamente nel protocollo stesso.

Facendo una simulazione in locale il tempo impiegato per generare in modo casuale e trasformare i 128 byte è quasi non misurabile.

Qualcuno ha parlato di kernel mode, signmifica che è possibile by passare lo schedulatore di windows?

il problema non è lo schedulatore di windows, i problemi sono


1) windows non è un sistema in real time quindi non garantisce il time constraint
2) il protocollo tcp-ip non è un protocollo per la trasmissione real time ne un protocollo affidabile nulla su tcp-ip ti garantisce la corretta trasmissione dei dati al primo tentativo ne ti garantisce di essere collision free, inoltre tcp-ip non è tempo deterministico il tempo di trasmisisone è casuale cosa che per le acquisizioni real time è quanto di peggio puoi avere, 200ms è un tempo ragionevolmente corretto per un sistema non realtime su tcp-ip difficile andar sotto a meno che non cambi protocollo e sistema operativo e questo è indipendente dal carico computazionale, operazioni del genere non generano nessun problema su un microcontrollore figurati su una cpu desktop il tuo problema non è computazionale ma di architettura

[marco.r]

Originariamente inviato da !fazz

il problema non è lo schedulatore di windows, i problemi sono


1) windows non è un sistema in real time quindi non garantisce il time constraint
2) il protocollo tcp-ip non è un protocollo per la trasmissione real time ne un protocollo affidabile nulla su tcp-ip ti garantisce la corretta trasmissione dei dati al primo tentativo ne ti garantisce di essere collision free, inoltre tcp-ip non è tempo deterministico il tempo di trasmisisone è casuale cosa che per le acquisizioni real time è quanto di peggio puoi avere, 200ms è un tempo ragionevolmente corretto per un sistema non realtime su tcp-ip difficile andar sotto a meno che non cambi protocollo e sistema operativo e questo è indipendente dal carico computazionale, operazioni del genere non generano nessun problema su un microcontrollore figurati su una cpu desktop il tuo problema non è computazionale ma di architettura

misterx non ha specificato se si tratta di valore medio o caso peggiore. Se siamo nel primo caso, SO realtime o non realtime dubito possa fare la differenza.
200 ms mi sembrano sono tantissimi anche per un ambiente non realtime (non ho esperienza su windows, ma in linux si riesce ad ottenere casi pessimi inferiori di un paio di ordini di grandezza )

[misterx]

la misurazione lh' effettuata prelevando il clock di sistema in millisecondi all'inizio del ciclo e alla fine del ciclo.

Il problema è che la funcione che ho e ce mi permette di leggere lo stato dei segnali, mi passa un byte alla volta quindi devo ciclare 128 volte e se è come credo, la costruzione di 128 pacchetti TCP/IP fa spendere tempo.

Ci fosse stata una funzione per avere i 128 byte in un solo invio l'avrei usata, ma non c'è.

Per tale motivo devo almeno scrivere un programma che non appesantisca ulteriormente

ciao

[marco.r]

Originariamente inviato da misterx

la misurazione lh' effettuata prelevando il clock di sistema in millisecondi all'inizio del ciclo e alla fine del ciclo.

Il problema è che la funcione che ho e ce mi permette di leggere lo stato dei segnali, mi passa un byte alla volta quindi devo ciclare 128 volte e se è come credo, la costruzione di 128 pacchetti TCP/IP fa spendere tempo.

Ci fosse stata una funzione per avere i 128 byte in un solo invio l'avrei usata, ma non c'è.

Per tale motivo devo almeno scrivere un programma che non appesantisca ulteriormente

ciao

yuck, ora capisco .
Quindi devi fare una richiesta TCP, e attendere la risposta per ogni singolo valore ? Cosi' non ne andrai fuori... dovresti perlomeno poter leggere tutti i valori in una sola chiamata oppure configurare la periferica di acquisizione in modo che ti spari di continuo i valori senza dover fare richiesta esplicita.
Di che periferica si tratta ? E' un prodotto commerciale ?

[misterx]

Originariamente inviato da marco.r

yuck, ora capisco .
Quindi devi fare una richiesta TCP, e attendere la risposta per ogni singolo valore ? Cosi' non ne andrai fuori... dovresti perlomeno poter leggere tutti i valori in una sola chiamata oppure configurare la periferica di acquisizione in modo che ti spari di continuo i valori senza dover fare richiesta esplicita.
Di che periferica si tratta ? E' un prodotto commerciale ?

sono microcontrolli

[misterx]

edit

[marco.r]

Originariamente inviato da misterx

ora leggendo i vari byte e costuendo l'array devo costuire i dispositivi associati.
In pratica devo vedere l'array come una stringa binaria lunga 1024 bit, ogni dispositivo è formato da bit sparsi nella stringa.

dispositivo1=bit1, bit100, bit98, bit127
dispositivo2=bit512, bit890, bit122

etc....

quando leggo la prima volta la stringa ho una deerminata situazione e pongo un tempo t per ogni bit del dispositivo; ad una successiva scansione sse il bit è cambiato verifico il tempo rispetto ad uno campione: che struttura si presta meglio per un lavoro del genere?

Dato un dispositivo, che senso avrebbe verificare

if(dispositivo1[numero_bit_precedente] != dispositivo1[numero_bit_attuale]) verifica se tempo di attivazione è diverso da quello campione

non impiegherebbe molto tempo una soluzione del genere ?

Ci sono alcune cose che non capisco:
tu devi monitorare lo stato dei singoli bit o ti basta tenere il timestamp di ogni apparato che cambia ?
Nel secondo caso puoi procedere utilizzando degli array, ad esempio
- Leggi gli array
- Scorri l'array in cerca dei bit che sono stati modificati, per ognuno di questi aggiorni il time

if (bit(A,n) != bit(prev_A,n) )
    dispositivo[bit(A,b)].timestamp = blabla;

- Fai una copia degli array per la prossima iterazione

Il trucco sta fondamentalmente nel precomputare piu' cose possibili compatibilmente con la ram a disposizione, ad esempio ad esempio un bel array che ad ogni i-esimo bit associa il relativo dispositivo a cui appartiene), od espandere l'array di bit in array di bool in modo da far meno conti ad ogni accesso.
Quest'ultima cosa pero' dipende anche dalle caratteristiche dei segnali... ad esempio se ci sono pochi bit a 1 oppure i segnali cambiano poco, ci sono metodi alternativi che potrebbero risultare piu' snelli.

In ogni caso rimane il problema iniziale: secondo me non riuscirai ad ottenere i tempi che ti interessano perche' se li mangia tutti la comunicazione via rete... hai provato a misurare i tempi della sola ricezione, commentando tutta l'elaborazione successiva ?

[misterx]

Originariamente inviato da marco.r

Ci sono alcune cose che non capisco:
tu devi monitorare lo stato dei singoli bit o ti basta tenere il timestamp di ogni apparato che cambia ?

devo monitorare lo stato di ogni singolo bit e il suo tempo di variazione

1             ________
             |        |
0 -----------+        +-----------------

però vanno raggruppati con una certa logica, difatti ad ogni dispositivo competono un certo numero di bit i quali sono sparpagliati nell'array letto.

L'idea è usare un array per ogni dispositivo