Şərif Super Kompüter

SSC, Şərif Universitetində hazırlanmış superkompüterdir və $2$ idarəçi və $n$ işçi prosessorundan ibarətdir. Bu, proqram təminatını paralel şəkildə işlədə bilir: idarəçi prosessorlardan biri proqramı işçi prosessorlara yükləyir və burada onların yaddaş və CPU istifadəsi balanslaşdırılır, digər idarəçi isə sistemi nəzarət altında saxlamaq üçün istifadə olunur.

Proqram təminatının müxtəlif hissələri arasında asılılıqlar olduğuna görə, prosessorlar arasında çoxlu mesajlar mübadilə olunmalıdır. Mesaj ötürülməsinin gecikməsini minimuma endirmək üçün çox sürətli bir şəbəkə tələb olunur. Şəbəkənin optimallaşdırılması üçün klika strukturu qurulacaq; burada hər bir prosessor cütü arasında birbaşa ünsiyyət kabeli olacaq.

İki fərqli kabel var: mavi kabellər, onlar saniyədə $100$ Megabit ötürə bilər, və qırmızı kabellər, onlar saniyədə $1$ Gigabit ötürə bilər. Hər bir işçi prosessor cütü bir mavi kabel ilə birləşdiriləcək. İdarəçi prosessorlarda daha yüksək ünsiyyət həcmi olduğuna görə, iki idarəçi bir qırmızı kabel ilə birləşdiriləcək və həmçinin hər idarəçi hər bir işçi ilə əlavə bir qırmızı kabel vasitəsilə birləşdiriləcək.

Beləliklə, SSC n + 2 ana platasından ibarətdir; hər birində məhz bir prosessor, lazım olan yaddaş və eyni zamanda üfüqi düzülmüş şəkildə n + 1 eyni şəbəkə yuvası quraşdırılmışdır. Ana platlar şaquli bir rəf qutusuna, hərəsi bir üfüqi rəfə yerləşdirilir. Beləliklə, hər ana plata, rəfdəki hündürlüyü ilə unikal şəkildə müəyyən edilir.

Soyutma sistemi bizi iki idarəçi ana platanı rəfin ən aşağı və ən yuxarı rəflərinə yerləşdirməyə məcbur edib. Qəbul edirik ki, aşağıdakı idarəçi $0$ hündürlüyündə, qalan ana platların hündürlükləri isə $0$-dan böyük tam ədədlərdir. Bir kompüter mühəndisi kimi, SSC-nin son yığımı sizə həvalə edilir. Sizə boş rəf qutusu və hazır ana platalar verilir və tapşırıq budur ki, ana plataları qoyulanlara və kabel uzunluqlarına uyğun yerləşdirib-yerləşdirə bilməyəcəyinizi müəyyən edəsiniz.

Dəqiq olaraq 2n + 1 sayda verilmiş ölçülərdə qırmızı kabel var. Lakin mavi kabellər $m$ fərqli ölçüdə mövcuddur və hər bir ölçüdə kabelin sayı məhdudiyyətsizdir. Siz kabellərin səliqəli və tarımlı çəkilməsinə çox diqqət edirsiniz; beləliklə, ana plataların hündürlükləri elə seçilməlidir ki, hər iki ana plata arasındakı kabelin uzunluğu onların hündürlük fərqinə tam bərabər olsun.