Partitioneringsmetoder

Partitioneringsmetoder er tilnærminger for å dele et sett, en datastrøm eller en løsning i mindre, disjunkte deler. Hensikten er ofte å forbedre ytelse, skalerbarhet eller håndterbarhet ved å redusere kommunikasjon mellom delene, oppnå bedre lokalitet og forenkle vedlikehold. Metodene brukes i grafteori, databaser og operativsystemer.

I grafpartitionering deles en graf inn i k grupper slik at hver gruppes størrelse er balansert og antall grensekryss mellom grupper er minimalt. Dette reduserer kommunikasjonskostnader i parallelle beregninger og nettverksdesign. Vanlige algoritmer inkluderer multilevel-metoder (for eksempel METIS), Kernighan–Lin og Fiduccia–Mattheyses.

I databaser og lagringssystemer refererer partitionering til å dele tabeller eller datafiler mellom noder. Vanlige strategier er range-partisjonering (basert på verdier i et felt), hash-partisjonering og list-partisjonering. Fordelene er bedre skalerbarhet og lokalt søk; utfordringer inkluderer data-skew og behov for rebalansering ved vekst eller endringer i tilgangsmønstre.

I minne- og operativsystemer kan partisjonering referere til inndeling av minnet i adskilte regioner for isolasjon eller for å støtte segmentering og paging. Fast partisjonering deler minnet i forhåndsdefinerte blokker, mens dynamisk og virtuell partisjonering gjør plass tilgjengelig etter behov. Partisjonering påvirker hukommelsesstyring, caching og ytelse i sanntidssystemer og i virtuelle maskiner.

Viktige mål og utfordringer inkluderer balanse mellom delene, reduksjon av grensekryss og god datalokalitet. Mange systemer bruker dynamisk omfordeling (rebalance) for å opprettholde krav etter hvert som arbeidsbelastningen endres.