Stort eeprom till datorn, låg accesstid.

[strombom]

Jag undrar, precis som sodjan, varför det krävs så kort accesstid? Varför går det inte att behandla data i pipeline... Det måste ju finnas alternativa lösningar

[Hemavan]

Lite offtopic men skulle windows köras snabbare på ett CF kort istället för hårddisk?

[8051guru]

Jag undrar, precis som sodjan, varför det krävs så kort accesstid? Varför går det inte att behandla data i pipeline... Det måste ju finnas alternativa lösningar :)

Det är en datastruktur där man har ett antal miljoner element, som pekar på varandra kors och tvärs. Ett element som ser ut på ett visst sätt, pekar på alla element som liknar detta element. Varje element skall peka på kanske upp till 50 andra element. Det går inte att lägga alla liknande element i sekvens, på grund av att elementen kan likna varandra i en massa olika avseenden. Vilket likhetsavseende man behöver följa upp vet man inte på förhand (dvs när man lägger upp datastrukturen). Liksom, vilken egenskap skulle man sortera på?

Jag kan med den frågan bara påvisa att det finns icke-triviala datastrukturer, och dessa kan inte pipelinas.

Jag kan inte förklara bättre, men jag ska ge ett bra exempel: Ett datorprogram. Varför kan man inte bara pipelina körningen av ett datorprogram? Varför måste man hålla på och hoppa fram och tillbaka? I själva verket är det helt onödigt med internminne i datorn. Det är bara en konspiration från minnestillverkarna. Bara magnetband är nödvändiga. Eller är det inte så.

[TERdON]

Och var kom de hårda realtidskraven in i bilden? Som krävde att du ALLTID hade en accesstid på max 1-10 mikrosekunder?

[sodjan]

Ligger pekarna till de andra elementen lagrade tillsammans
med varje element ? Eller som separata index ?

Med "flera miljoner" element behöver du 4-bytes pekare.
Med upp till 50 pekare per element behövs det alltså 200 bytes
bara för pakerna (tillkommer själva elementet självt). Var kommer
de 16-bytes strukturer som nämndes i början in i bilden ?

Jag ser inte varför inte dessa data skulle kunna lagras som en
traditionell rellationsdatabas med index för att knyta ihop de
olika rellationerna.

Det som verkar mest underligt är dock mikrosekunds-kravet. Det
är inte helt klart på vilken nivå det ska tolkas, enbart access ur själva
lagringsmediat eller hela vägen till applikationen (hur nu den ser ut)...

[8051guru]

Och var kom de hårda realtidskraven in i bilden? Som krävde att du ALLTID hade en accesstid på max 1-10 mikrosekunder?

Jag sa inte max access tid. Det som har betydelse här, är den genomsnittliga accesstiden. Min användning av ordet stämmer med wikipedia.

[8051guru]

Ligger pekarna till de andra elementen lagrade tillsammans
med varje element ? Eller som separata index ?

Med "flera miljoner" element behöver du 4-bytes pekare.
Med upp till 50 pekare per element behövs det alltså 200 bytes
bara för pakerna (tillkommer själva elementet självt). Var kommer
de 16-bytes strukturer som nämndes i början in i bilden ?

Jag ser inte varför inte dessa data skulle kunna lagras som en
traditionell rellationsdatabas med index för att knyta ihop de
olika rellationerna.

Det som verkar mest underligt är dock mikrosekunds-kravet. Det
är inte helt klart på vilken nivå det ska tolkas, enbart access ur själva
lagringsmediat eller hela vägen till applikationen (hur nu den ser ut)...

Pekarna lagras i den nuvarande implementationen i en länkad lista, dvs uppdelad i mindre block. Själva elementet blir i storleksordningen 16 byte.

(Ja, jag har redan en implementation, men jag kan inte köra den på rätt datamängd.)

Det är en relationsdatabas, men jag använder ingen motor.

Accesstiden till applikationen är det som har betydelse.

[sodjan]

OK, jag får inte riktigt ihop det, och jag vet inte om det har någon
betydelse, men i alla fall...

Så en "länkad lista" innehåller de element som "liknar" varandra.
Så långt är jag med, varje element har *en* pakare till nästa element i listan.

Men sen skrev du att "elementen kan likna varandra i en massa olika avseenden."

Alltså måste det antingen finnas kopior av samma element om de dels
enbart ska innehålla *en* pekare, dels ska finnas i *flera* länkade listor.

*Eller* så måste varje element ha plats för ett *antal* pakare, lika många
som det antal länkade listor som just det elemantet är medlem i. D.v.s
"en massa" pakare.

Jag får inte ihop det med "Själva elementet blir i storleksordningen 16 byte."...

Jag har jobbat med databasdesign och drift i 15 år, därav mitt intresse...

[TERdON]

Jag sa inte max access tid. Det som har betydelse här, är den genomsnittliga accesstiden. Min användning av ordet stämmer med wikipedia.

Sorry, då har jag missförstått, jag förstod det som att det var ett krav på max accesstid (normalt är accesstid för en viss typ av minne ganska väldefinierad även om den varierar något). Engelskspråkiga Wikipedia definierar hur som helst INTE accesstid som du säger utan endast fördröjningen mellan förfrågan och svar. Däremot anges där även exempel på medelvärden för accestider (average latency), vilket är rätt naturligt. Accesstiderna för en viss typ av minne är relativt konstant över tiden, om minnet inte är baserat på mekaniska delar, som en hårddisk.

Hur som helst, om det är som du säger att det bara är den genomsnittliga prestandan som är viktig så ser jag inte riktigt varför du inte ska kunna använda en flashdisk även om den har en accesstid på en bra bit över 10 mikrosekunder, det kommer ju motverkas av cachning i RAM-minnet.

Kort sagt, om accesstiden är 0,1 ms för slumpvist valt element (där har vi vår IDE-flashdisk!) och du har en cache-träff-andel i RAM på 90%, så (eftersom accesstiden för RAM i sammanhanget är försumbar) får du en genomsnittlig accesstid på 10 mikrosekunder. Om du proppar datorn full med RAM-minne (4 eller 8 GB kanske) verkar en accessträffsandel på runt 90% inte alltför otrolig, ens med väldigt slumpmässig data (finns hur mycket vetenskaplig forskning och studier om nyttan med olika typer av cache-funktioner som helst, och du har typiskt sådana träffandelar även i CPU-cachen!). Så med en snabb flash-IDE-disk och mycket RAM så borde du kunna nå i alla fall den nedre delen av hastigheterna du eftersträvar, i genomsnitt. Fortfarande inte billigt men i alla fall överkomligt.

EDIT: skrev om inlägget eftersom jag knappt förstod vad jag menade själv

[strombom]

Det låter spännande!

En FPGA + en massa SDRAM på PCI bussen ? Det kanske redan finns såna kort?

Edit: det hade ni redan tagit upp..