sslug-teknik team mailing list archive

["Anders S. Johansen" <sewerin@xxxxxxxxxx>]

Mads Bondo Dydensborg wrote:
> > overvejer rød/blå træer, da jeg i forbindelse med infosøgning om STL
> > fandt ud af, at de brugte denne form for ballancerede binære træer. De
> > er vist opfundet efter min tid på algoritmik i 1991... :D
> STL implementationerne af mange af de her ting er -meget- hurtige.

> > > Det du vil er vel da tråde... check man pthread_create under Linux for > > > en oversigt.
> >
> > Jeg er ikke så vild med kernetråde i denne sammenhæng, da en hel del af
> > min argumentation hænger på at de eksisterende systemer holdes nede
> > performance-mæssigt af for mange kontekstskift. På den anden side får
> > jeg jo brug for nogle processer til at overvåge de forskellige sockets,
> > så jeg slipper vel ikke udenom.
> 
> I *princippet* kan du jo skrive din egen scheduler - altså, select og
> mange andre io ting kan jo laves ikke-blokerende. Så du kan jo høvle
> igennem select en gang imellem for at finde data, og kun hente hvis
> nødvendigt. På den måde slipper du for at have kontekst skift, der
> *smadrer din cache*, hvilket er det eneste rigtigt dyre. (Burde det være
> ihvertfald. Registerskift burde være meget hurtige, men cachen gør av).

Godt set! Det er netop det med at samdre cachen, der er problemet på de
fleste systemer af denne type. Algoritmerne sutter, rent ud sagt.
Eksempel:

Hvordan finder man ud af, hvad en process har skrevet til lageret siden
sidste synkronisering (lock eller barriere)?

Hmm. Vi erklærer da bare hele lageret som skrivebeskyttet gennem MMU.
Når processen prøver at skrive til en side, trapper vi til kerne. Dette
signal samler vi op, laver en kopi af lagersiden (dyrt), som vi ved
kommende synkronisering kan sammenligne med sidens indhold til den tid
(dyrt!), og komprimere med RLE (DYRT!) for at spare båndbredde (på et
100MBit/sek net???). Disse "diffs" kan så merges, så disjunkte
skrivninger til en side kan udføres mellem synkroniseringer.

At dette kun bruges på sider flere knuder ønsker at skrive til, er ingen
undskyldning. Sjovt nok skalerer den slags systemer ikke så godt :)

Anden metode sutter også: Kræv at alt delt lager erklæres "shared", og
at programmøren ved synkroniseringspunkter explicit markerer, hvad der
skal opdateres. Hvor meget nemmere end message passing er det? Ikke
særligt... Og så kræver det "lige" at du laver en specialcompiler. Det
er jo "let" liget at lave en god optimerende compiler, ikke?

Tredje metode sutter også: Antag at compileren vil være i stand til at
afdække informationen fra anden metode statisk ved oversættelse. Samme
kommentarer om compiler, men dette er tydeligvis umuligt. Aliasproblemer
forhindrer den slags dataflow-analyse på en uniprocessor allerede, så
mon ikke det er umuligt i et distribueret system? Resultat: Al delt
memory bliver erklæret "opdateres" ved synkronisering = systemet slæbes
til et knasende stop af irelevante opdateringer.

Fjerde metode: Mobile objekter og single-writer. Og hvordan sikrer man
så at flere knuder kan deles om et objekt, som f.eks. en matrice?
Resultat: Dårlig skalerbarhed.

Min metode: Annotering af læsninger og skrivninger til delt lager = brug
primitiver. Besværligt for programmøren, men burde skalere fint. 

Der er som sagt et speciale i programudviklingen alene, så hvis du keder
dig er du da velkommen :D I thought not...

And

PS: Nævnte jeg at mange af disse folk har udviklet deres egen protokol,
da de mente TCP var for ineffektiv? Sjovt nok fande de fleste af dem ud
af, at når de var færdig havde de en forbindelsesorienteret reliable
protokol med flow-control, som kørte langsommere end TCP. 30 års
optimering er ikke at kimse af - vel?
-- 
Anders S. Johansen, Jagtvej 109, 3.tv, 2200 Kbh. N +045 35836565
Wisdom = TANJ + TANSTAAFL