Kaavion jakaminen

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 24. maaliskuuta 2017 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Graafin osiointi aligraafiksi ( eng. Graph partitio ) (joskus käytetään kirjallisuudessa myös termiä graafin leikkaaminen [1] ) on esitys alkuperäisestä graafista pisteiden osajoukkojen joukkona tiettyjen sääntöjen mukaisesti. Yleensä tehtävän ehdon mukaan vaaditaan , että , eli alkuperäisen graafin kaikki kärjet on jaettava osajoukkojen kesken, ja . Yleensä osion ortogonaalisuuden vaatimus otetaan lisäksi käyttöön : eli sama kärki ei voi olla osa eri osajoukkoja. Joskus mahdollisten osioiden joukosta on valittava sellainen, joka täyttää rajoitukset ja on optimaalinen (tai alioptimaalinen) ilmoitetun kriteerin mukaan, tai todistettava, että vaadittua osiota ei ole olemassa (rajoitukset ovat epäjohdonmukaisia). Graafin osiointitehtävä kuuluu luokkaan NP-complete , osioiden lukumäärän yläarvio määräytyy Bell-luvun mukaan, mutta yleensä kaikki mahdolliset osiot eivät ole oikein (ei riko rajoituksia), eli arvio on yliarvioitu. Kun graafin kärkipisteiden lukumäärä on yli 15–20, optimaalisten osioiden saaminen on yleensä mahdotonta hyväksyttävässä ajassa (joskus tähän käytetään haara- ja sidontamenetelmää ), joten käytännössä ne rajoittuvat heuristiikan avulla saatuihin alioptimaalisiin ratkaisuihin. algoritmeja . $G=\vasen\kulma A,V\oikea\kulma$ $\mathrm {Sep} ~A=\left\{A_{1},A_{2},...,A_{n}\oikea\},A_{i}\subseteq A$ $\bigcup _{i=1}^{n}A_{i}=A$ $A_{i}\neq \varnothing$ $\forall i\neq j~A_{i}\cap A_{j}=\varnothing$ $N=\left|A\right|$

Tarve hankkia osio syntyy, kun ratkaistaan useita ongelmia:

Graafin väritysongelma — jokainen kärkijoukko koostuu samanvärisistä pisteistä, ja samanvärisillä pisteillä ei ole yhteisiä sattuvia reunoja. Yleensä kiinnostaa löytää minimivärjäys, joka yleensä on NP -luokan ongelma (optimaalisuuskriteeri on ). $V_i$ $n\rightarrow \min$
Ongelma graafin yhdistettyjen komponenttien lukumäärän ja koostumuksen määrittämisessä .
Paikallisen verkon topologiaa suunniteltaessa sen jako yleislähetysalueisiin määräytyy suorituskykyvaatimusten mukaan (optimaalisuuskriteeri on toimialueiden välisen liikenteen määrä, kun käytetään erilaisia palvelimia ja verkkopalveluita (pääsy tiedostopalvelimiin , DHCP , WINS , DNS jne. .), rajoitukset - kytkimien , reitittimien ja viestintäkanavien porttien määrä ja kaistanleveys sekä hinta).
Painettujen piirilevyjen tai mikropiirien keskinäisten kytkentöjen jäljittämisongelmassa on välttämätöntä jakaa alkuperäinen piiri kerroksiin (joista jokainen on tasokaavio ). Optimaalisuuskriteerit - kerrosten ja liitäntöjen vähimmäismäärä (itse asiassa tuotantokustannukset), rajoitukset - elektronisten komponenttien kokonaismitat ja vaatimukset lämpö- ja sähkömagneettiselle yhteensopivuudelle. [2]
Tehtävässä algoritmin graafisen kaavion jakaminen lohkoiksi toteuttamista varten moniprosessorijärjestelmässä tai loogisessa moniohjaimessa . Optimaalisuuskriteerit ovat lohkojen vähimmäismäärä, mikrotoimintasignaalien ja loogisten ehtojen kopioinnin vähimmäisaste, moduulien välisten ohjaussiirtojen vähimmäismäärä, moduulien välisen ohjauksen ja tiedonsiirron vähimmäisliikenne; rajoitukset määräytyvät käytetyn elementtipohjan mukaan. [3] [4] [5] [6]
Graafin esitys taso-rinnakkaismuodossa tai algoritmin kaaviokaavio osien joukon muodossa (osien kärkijoukot voivat olla ei-ortogonaalisia).
Algoritmigraafin jakaminen ei-leikkaaviin aligraafiin ja niiden sijoittaminen prosessorielementteihin tai FPGA :n elementteihin toteutettaessa dataliukuhihnakäsittelyä (kuormituksen tasapainotus). [7] [8]

Kuvaajan osiointimenetelmät [9]

Koordinaattiosio
Rekursiivinen inertiapuolittajamenetelmä
Verkkojako Peano-käyrillä
Liitettävyyden jakaminen (lähinnä leveyshaku )
Kerniganin

Katso myös

Gerasim@Home

Muistiinpanot

↑ Evstigneev V. A. Graafiteorian soveltaminen ohjelmointiin. M.: Nauka, 1985. 352 s.
↑ Kureichik V. M., Glushan V. M., Shcherbakov L. I. Kombinatoriset laitteistomallit ja algoritmit CAD:ssa. Moskova: Radio ja viestintä, 1990. 216 s.
↑ Baranov S. I., Zhuravina L. N., Peschansky V. A. Menetelmä algoritmien rinnakkaisten graafisten kaavioiden esittämiseksi peräkkäisten graafisten kaavioiden sarjoilla // Automation and Computer Science. 1984. Nro 5. S. 74-81.
↑ Zotov I. V., Titov V. S., Koloskov V. A. [et al.] Mikroohjelmien monimikro-ohjainten organisointi ja synteesi. Kursk: Kustantaja "Kursk", 1999. 368 s. ISBN 5-7277-0253-4
↑ Vatutin E. I., Zotov I. V., Titov V. S. [et al.] Kombinatorialis-loogiset ongelmat rinnakkaisten logiikkaohjausalgoritmien osioiden syntetisoinnissa loogisten monisäätimien suunnittelussa. Kursk, Kurskin valtion teknillisen yliopiston kustantamo, 2010. 200 s. ISBN 978-5-7681-0523-5
↑ Vatutin E.I. Loogisten monisäätimien suunnittelu. Algoritmien rinnakkaisten graafisten osien synteesi. Saarbrucken : Lambert Academic Publishing , 2011. 292 s. ISBN 978-3-8433-1728-3
↑ Kaljajev I. A., Levin I. I., Semernikov E. A., Shmoylov V. I. Uudelleenkonfiguroitavat moniputkiset laskentarakenteet: 2. painos. Rostov n/a: YuNTs RAN, 2009. 344 s. ISBN 978-5-902982-61-6
↑ Kalyaev I. A., Levin I. I. Uudelleenkonfiguroitavat moniputkilaskentajärjestelmät tietojenkäsittelyn ja ohjauksen virtausongelmien ratkaisemiseen // 5. kansainvälisen konferenssin "Parallel Computing and Control Problems" (PACO'10) täysistuntoraportit. M.: IPU RAN, 2010, s. 23-37.
↑ INTUIT.ru: Kurssi: Teoria ja käytäntö ..: Luento nro 10: Rinnakkaiset menetelmät kaavioissa (pääsemätön linkki)