
dou pedon kaa prasaran

dou-vriksh prasaran (sankshipt 2-vriksh-prasaran yaa 23-prasaran) ack algorithm haye joe sandesh paarit karane kaa upayog karke ack vitarit pranali parr ack prasaran sanchaar pattern koo lagu kartaa haye.
prasaran ack aam taur parr upayog kiya jaane vaalaa saamoohik sanchaalan haye joe ack processor seey anya sabhi processors koo detta bhejata haye.
dou-pedh prasaran dou dwiaadhaari pedon parr samvarti roop seey sanchaarit hotaa haye joe sabhi processors mein faile hotey hain. yeh poorna-dwigunit sanchaar model mein bandwidth kaa poorna upayog praapt kartaa haye jabaki bhaag lene vaale processors kii sankhya mein ack praarambhik vilambata laghuganak hotaa haye.
algorithm koo ack kamee yaa upsarg raashi karane key liye bhee anukoolit kiya jaa sakata haye.
algorithm.
ack prasaran ack nirdisht root processor seey anya sabhi processors koo ack sandesh bhejata haye.
"dwiaadhaari vriksh prasaran" ack dwiaadhaari vriksh kaa upayog processor key beach sanchaar koo model karane key liye kartaa haye.
pratyek processor pedh mein ack node seey mell khaata haye, aur root processor pedh kii jarh haye.
ack sandesh prasaarit karane key liye, mool apane dou bachchon (child nodes) koo bhejata haye. pratyek processor taba taka prateeksha kartaa haye jaba taka kii vaha praapt naheen curr letaa aur phir apane bachchon koo bhejata haye. kyonki pattiyon key koee bachche naheen hotey hain, unhein koee sandesh bhejane kii aavashyakta naheen hoti haye.
prasaran prakriya koo sandesh koo khandon mein vibhajit karke pipelined kiya jaa sakata haye, jinhen phir lagaatar prasaarit kiya jaataa haye.
aise dwiaadhaari vriksh mein, vriksh key patte kewal detta praapt karate hain, lekin kabhi bhee swayam koee detta naheen bhejate hain. yadi sanchaar dwidishaatmak (poorna-dwigunit) haye, jiska arth haye kii pratyek processor ack sandesh bhej sakata haye aur ack hii samay mein ack sandesh praapt curr sakata haye, tou pattiyaan upalabdh bandwidth kaa kewal aadhaa upayog karati hain.
dou-pedh prasaran kaa vichaar dou dwiaadhaari pedon kaa upayog karna aur donon parr samvarti roop seey samvaad karna haye.
pedon kaa nirmaan iss tarah kiya jaataa haye kii ack pedh key aantarik node dusare pedh key patte key node key anuroop houn.
jiss detta koo prasaarit kiya jaanaa haye, usey samaan aakar key khandon mein vibhajit kiya jaataa haye.
algorithm key pratyek charan mein, pratyek processor koo ack block praapt hotaa haye aur pichhale block koo usake bachchon mein seey ack koo usa pedh mein bhejata haye jisamen yeh ack aantarik node haye.
ack anusuchi kii aavashyakta hoti haye taaki kissy bhee processor koo ack hii charan mein dou sandesh bhejane yaa praapt karane naa padey.
aisee anusuchi banaane key liye, donon pedon key kinaaron koo 0 aur 1 key saath iss tarah seey rangaa jaataa haye kii
rung 0 vaale kinaaron kaa upayog summ charanon mein kiya jaataa haye, rung 1 vaale kinaaron kaa upayog visham charanon mein kiya jaataa haye.
yeh anusuchi pratyek processor koo ack sandesh bhejane aur pratyek charan mein ack sandesh praapt karane kii anumati detee haye, poori tarah seey upalabdh bandwidth kaa upayog karati haye.<bee. aar.>
maan leejiye kii processor ack sandesh prasaarit karna chaahata haye. shesh prakramkon key liye dou pedon kaa nirmaan kiya gayaa haye. processor dou pedon kii jadon koo baari-baari seey block bhejata haye, isaliye pratyek pedh sandesh kaa aadhaa prasaran kartaa haye.
vishleshan.
maan leejiye kii prasanskaran tatvon (pee. ee.) kii sankhya, seey seey sankhya mein.
pedon kaa nirmaan.
jaane dou.
 aur ise oonchaai key pedon key roop mein banaaya jaa sakata haye, jaise kii donon pedh nimnalikhit vidhi key saath processor kii ack crum sankhya banaate hainh
shifting" key saath, pahale iss tarah seey banaaya jaataa haye, sivaay isake kii isamen ack atirikt processor hotaa haye. phir ack sthiti seey baain or sthanantarit kiya jaataa haye aur sabse baain or kaa patta hataa diyaa jaataa haye.
darpan" key saath, (processor aur key beach darpan aksh key saath) kii darpan chhavi haye. darpan kewal summ key liye kaam kartaa haye.
yeh saabit kiya jaa sakata haye kii sabhi key liye vaanchhit gunon key saath ack rung maujood haye.
jaba darpan kaa upayog nirmaan key liye kiya jaataa haye, tou pratyek processor swatantra roop seey samay parr apane ghatana kinaaron key rung kii ganana curr sakata haye.
sanchaar kaa samay.
iss vishleshan key liye, nimnalikhit sanchaar model kaa upayog kiya jaataa haih ack aakar key sandesh kaa sanchaar samay hotaa haye, joe swatantra hotaa haye jiss parr processor samvaad karate hain. sandesh bhejane key liye startup overhead kaa pratinidhitva kartaa haye, prati detta tatva sancharan samay kaa pratinidhitva kartaa haye.
maan leejiye kii aakar kaa sandesh khandon mein vibhajit haye. pratyek sanchaar kadam mein samay lagata haye.
processor parr jarh aur usake neeche dou pedon key saath sanchaar sanrachana kii oonchaai honey dein. 
kadmon key baad, pahala detta block donon pedon key pratyek node taka pahunch gayaa haye. isake baad, pratyek processor koo harr charan mein ack block praapt hotaa haye jaba taka kii usey sabhi block praapt naheen hoe jaate.
kull charanon kii sankhya key parinamswarup kull sanchaar samay hotaa haye.
ack ishtatam kaa upayog karate hue, kull sanchaar samay haye.
samaan algorithm kii tulanaa.
ack raikhik pipeline prasaran mein, sandesh koo khandon mein vibhajit kiya jaataa haye. pratyek charan mein, pratyek processor koo processor seey ack block praapt hotaa haye aur processor koo ack block bhejata haye.
raikhik pipeline mein ishtatam thruput hotaa haye, lekin isamen ack startup samay hotaa haye.
badey paimaane parr, dou-pedh prasaran kii praarambhik vilambata tej haye.
kyonki donon algorithm mein ishtatam thruput hotaa haye, isaliye badee sankhya mein processor key liye dou-vriksh algorithm tej hotaa haye.
ack dwipadi vriksh ack dwipadi vriksh key saath sanchaarit hotaa haye. pratyek prakriya prasaarit sandesh praapt karati haye (mool mein pahale seey hii sandesh haye) aur phir apane bachchon koo sandesh bhejati haye.
ack dwipad vriksh prasaran mein dou-vriksh prasaran kaa kewal aadhaa praarambhik samay hotaa haye, lekin adhik sanchaar kaa ack kaarak hotaa haye.
dwipad vriksh prasaran chhote sandeshon key liye dou-vriksh prasaran kii tulanaa mein tej haye, lekin badey sandeshon key liye dheema haye.
ack pipelined dwiaadhaari vriksh prasaran sandesh koo khandon mein vibhajit kartaa haye aur ack dwiaadhaari vriksh parr lagaatar khandon koo prasaarit kartaa haye.
ack sadharan santulit dwiaadhaari vriksh key bajaay "fibonechi vriksh" kaa upayog karke, praarambhik vilambata koo cumm kiya jaa sakata haye.
ack oonche fibonacci pedh mein ack jarh hoti haye jisaki oonchaai fibonacci pedh key roop mein hoti haye aur ack fibonacci pedh isake daahine bachche key roop mein hotaa haye.
pipelined fibonechi tree prasaran mein dou-pedh prasaran kii aadhi praarambhik vilambata hoti haye, lekin thruput kaa kewal aadhaa hii hotaa haye.
yeh chhote sandeshon key liye tej haye, jabaki dou-pedh prasaran badey sandeshon key liye tej haye.
anya sanchaar adim key liye upayog.
kamee.
ack kamee (aim. pee. aaee. maanak mein cock _ 1) sootra _ 1 kii ganana karati haye jahan mool roop seey lambai kaa ack sadish haye.
processor aur formula _ 2 parr upalabdh ack dwiaadhaari operation haye joe sahayogi haye, lekin aavashyak roop seey commutative naheen haye.
parinam ack nirdisht root processor parr sangraheet kiya jaataa haye.
maan leejiye kii yaa. 
iss mamle mein sanchaar prasaran key samaan haye, sivaay isake kii sanchaar kii disha ulat haye.
pratyek prakriya apane bachchon seey dou block praapt karati haye, unhein apane swayam key block key saath cumm karati haye, aur parinam apane maataa-pitaa koo bhejati haye.
jarh jadon seey khandon koo praapt karane mein baari aatee haye aur unhein apane swayam key detta key saath cumm curr detee haye.
sanchaar kaa samay prasaran key liye samaan haye aur prati processor detta kii matra cumm hoe jaati haye.
yadi cumm karane kaa kaary parivartaniya haye, tou parinam kissy bhee mool key liye processors kii punah sankhya banaakar praapt kiya jaa sakata haye.
yadi operation commutative naheen haye aur root naheen haye yaa haye, tou sanchaar samay key liye ack nimn seema haye.
iss mamle mein, shesh processor koo dou upsamuhon mein vibhajit kiya jaataa haye. processor jarh mein kamee karate hain aur processor jarh mein kamee karate hain. upsamuhon kii dou jadon seey ack key baad ack prakramak khand praapt kartaa haye.
upsarg raashi.
ack upsarg yog (cock _ 2) pratyek key liye sootra _ 3 kii ganana kartaa haye
processor jahan mool roop seey lambai kaa vector haye
processor aur formula _ 2 parr upalabdh ack dwiaadhaari sahayogi sanchaalan haye.
ack inorder binary tree kaa upayog karke, ack upsarg yog kii ganana pahale ack upp-phase kaa pradarshan karke kii jaa sakati haye jisamen pratyek aantarik node baaen aur daaen sabse pattiyon key liye ack aanshik yog sootra _ 5 kii ganana kartaa haye aur usake baad ack down-phase hotaa haye jisamen formula _ 6 key upsarg koo pedh key neeche bheja jaataa haye aur pratyek processor koo apane upsarg yog kii ganana samaapt karane kii anumati dee jaati haye.
upp-phase mein sanchaar processor mein kamee key barabar haye aur down-phase mein sanchaar processor seey prasaran key barabar haye.
kull sanchaar samay dou-pedh prasaran key sanchaar samay seey lagbhag doguna haye.
ee. aiss. bee. tii. prasaran.
yadi dou kii shakti haye, tou ack atee-ghana mein dwipadi pedon (ee. aiss. bee. tii.) mein faile kinare key vikhandan parr adharit ack ishtatam prasaran algorithm haye.
jarh koo chhodkar atee-ghana koo ee. aiss. bee. tii. mein vibhajit kiya jaataa haye.
algorithm prasaran detta koo blocks mein vibhajit karke pipelining kaa upayog kartaa haye.
processor chakreeya roop seey ee. aiss. bee. tii. kii jadon mein block vitarit kartaa haye aur pratyek ee. aiss. bee. tii. ack pipelined dwiaadhaari vriksh prasaran kartaa haye.
charan mein, pratyek processor ayam key saath ack sandesh bhejata aur praapt kartaa haye.
algorithm kaa sanchaar samay haye, isaliye startup vilambata dou-pedh prasaran kii startup vilambata kaa kewal aadhaa haye.
<bee. aar.>
ee. aiss. bee. tii. prasaran kii kamee yeh haye kii yeh anya moolyon key liye kaam naheen kartaa haye aur ise (gair-commutative) kamee yaa upsarg yog key liye anukoolit naheen kiya jaa sakata haye.

