Bu sayfadaki yazılar
Sayfanın metni
Sayfa 25
Seçme başarısızlığının,
yazılım değil donanım tasarımcılarının kavraması ve çözümlenmesi gereken bir sorun olduğu sanılabilir. Bunun gerçekle hiçbir ilişkisi yoktur. Ortak datadan paralel işlerde yararlanılacağında, paralel bilgisayar programlayıcıları sürekli olarak seçme başarısızlıklarına çözüm bulma sorunuyla karşı karşıyadır.
Eindhoven Teknik Yüksek Okulu'ndan Edsger Dijkstra 1965'te paralel işlemcilerin kontrol edilmesi için yapılan girişimlerin yol açtığı yazılım sorunlarını öngören bir çalışma yayımladı (Dijkstra 1985). O zamandan bu yana, bütünüyle bu konuya ilişkin kitaplar yayımlanmıştır; bazı modern programlama dilleri de soruna ilişkin sentakslar içermektedir. Dijkstra sorunu şöyle dile getirir: Bir tek ortak belleğe bağlı N işlemciden oluşan bir bilgisayarı alın. Her işlemci kendi programını yürütür. Her program, tüm işlemcilerin ulaşabildiği datayı inceleyen ve değiştiren bir kod bölümü içerir. İki işlemcinin ortak dataya aynı anda varmasını önlemek gerekir, yoksa birbirlerine karışarak tutarsız sonuçlar çıkarırlar. Demek ki, öyle giriş (enter) çıkış (exit) protokolleri geliştirmek gerekiyor ki, işlemcilerin çalışma hızı sağlayacak analitik hızı ne olursa olsun, programların önemli kod bölümlerinin belleğe aynı anda ulaşmaları önlenebilsin ve çıkış protokollerinin aynı olması ve hangi işlemcilerin bunları kullanacağına dair hiçbir bilgi içermemeleri gerekir.
Basit bir örnek Dijkstra'nın önlemeye çalıştığı soruna açıklık getirecek.
“Ticari bankalarda, otomatik vezne makinası programlarında fonları hesaptan hesaba aktaran bir altprogram bulunur. X liranın A hesabından B hesabına aktarılması B=B+X” program cümleleriyle ifade edilebilir. Uygulama aşamasında A+B toplamı olduğu gibi korunarak, hesapların durumunun B'den (A-X, B+X)'e çevrilmesi beklenir. Şimdi, ben A'dan B'ye 1000 liralık bir transfer yaparken, karımın da (başka bir vezne makinasında) B'den A'ya 400 lira transfer ettiğini varsayalım. İşlemlerimizi hangi sırayla yaparsak yapalım, hesaplarımızın sonuçta alacağı durum (A=600, B=600) olacaktır. Ancak iki işlemcimizin bu ifadeler için makina kodunu aynı anda uygulanabileceğini düşünürsek o zaman şunlar olabilir: Benim işlemcimin A=1000 yazmasından sonra, B=1000 yazmasından ise önce, karımın işlemcisi devreye girerse ne olacak? A hesabına eklenecek ve hesap, A=1000+400=A=600 olacaktır. B'de ise yalnızca karımın yaptığı transfer kaydedilecek, yani B=400 durumunda kalacaktır. Demek ki, sorun şöyle de ifade edilebilir: Datayı inceleyen ve değiştiren kod kısmının bölünemez olması gerekiyor. Bu sorunu çözümlerken bellek donanımının, bir defada yalnız bir işlemcinin belleğe ulaşmasına fırsat veren seçiciler içermesinden yararlanır. Programlayıcı açısından bu, sayısal değişkenlerin yazılma ve okunmasının bölünemez bir işlem olduğu anlamına gelir. Dijkstra, ortak sayısal değişkenleri işlemciler arasında sinyal olarak kullanan, GİRİŞ(ENTER) ve ÇIKIŞ(EXIT), iki programın nasıl yazılabileceğini göstermiştir. Bu programların, içerdikleri tüm analitik kısımların birbirlerini karşılıklı olarak dışlamasını garanti ettikleri kesinlikle kanıtlanmıştır. Ayrıca bu çözümün anlamsız olmadığını, çünkü bir işlemcinin belli bir analitik kısmı serbest bırakmasından sonraki sınırlı süre içinde bir başkasının GİRİŞ işlemini tamamlayacağını göstermiştir.
Dijkstra'nın programları karmaşık ve anlaşılması güçtü. Ancak, bu programların çözümlediği seçme sorunlarının ciddiyeti kolayca anlaşılabiliyordu. Böylece bilgisayar mimarları daha dolaysız bir çözüm geliştirdiler. Donanım çözümü, bir kilit koyan özel bir komuttan yararlanır. Bu tek komut, Dijkstra'nın GİRİŞ protokolünde sinyal olarak kullanılan değişkenleri inceleyen döngüyle aynı işi görür. LOCK X komutu, bellek adresi X'i iki tabanlı bir değişken olarak ele alır. Eğer X=0 bulursa aynı bellek çevriminde X'e 1 değerini vererek işleme geçer. X=1 bulursa, komutu daha sonraki bir bellek çevriminde yeniden uygulamaya çalışır. ÇIKIŞ komutu ise sıradan bir CLEAR X'dir. Ancak bu çözümün çok sayıda işlemci üzerinde yaygınlaştırılmasında engel olan sınırlılıkları vardır. Birçok işlemci aynı anda programlarının kod kısmını devreye sokmaya çalışıyorsa, bunlardan biri dışında hepsi, X=0'ı okuyana dek “LOCK” komutunu yeniden sınayan bir döngü içine hapsolur. (Seçme devresi, X=0 olduktan sonra belleğe yalnızca birinin ulaşmasına fırsat verir.) Sorun, bu döngünün çevriminin bir bellek erişimi gerektirmesinden kaynaklanmaktadır. Bu ise, başka bir işlemcinin aynı bellek alanında saklanmış diğer değişkenlere ulaşmasını engeller. Bu da kilit kontrol döngüsünün görevini yerine getirmeye çalışan her işlemciye karışacağı anlamına gelir. Sistemdeki işlemcilerin sayısı arttıkça kilit kontroller artar ve sonuçta hiçbir işlemci görevini yerine getiremez olur. Çok işlemcili modern bilgisayar sistemlerinde aşırı kilit kontrol sorununa karşı iki çözüm uygulanmaktadır. 1985'te Dijkstra'nın öne sürdüğü ilk çözüm kilidin yerini semafor adı verilen bir sıralamanın almasıdır. Semafor kullandığı sırada GİRİŞ protokolüne yönelen bir işlemci geçici olarak durdurulur ve adı sıralamaya konur. ÇIKIŞ protokolü, eğer varsa, sıralanmış işlemcilerden birini serbest bırakır. İkinci çözümde, her işlemcinin gizli bölme adı verilen ve ana bellekteki değerlerin kopyalarını içeren kendi belleği vardır. Böylece LOCK X komutu gizli bölmesine kilit değişkeni kopya eder ve başka hiçbir işlemciye müdahale etmeden kontrol döngüsünü sürdürür. CLEAR komutu mesajını ilettiğinde, bu mesajı bekleyen işlemci belleklerinden yalnızca biri tarafından alınır. Her iki çözüm de bağlantı çekişmesini aza indirip belleğin makul sayıda işlemci tarafından paylaşılmasını sağlar. Aslında kaynakların kendisini kilitlemek, kaynağa ulaşmaya çalışan kodu kilitlemekten daha verimlidir. Bu iki işlemcinin kodlarının, farklı kaynakları kullandıkları sürece, çalışmaya devam etmesini mümkün kılar. Banka örneğinde, transfer alt-programında bir kilit kullanmak yerine, A ve B hesapları için ayrı ayrı kilitlerin kullanılması daha elverişli olur. Seçme sorununda yazılıma ilişkin çözümlerinin de sonunda, sonraki bellek devrinde hangi işlemcinin belleğe ulaşacağına karar veren donanım seçicilerine dayanır. Bu nedenle, yazılım seçmesinin güvenirliği seçicinin güvenirliği ile sınırlıdır.
Klavyeyle gezinmek için ← ve → tuşları.
Sayfa 24
Peter J. Denning'ten Çeviren Nilüfer Güngören
14. yüzyıl Jean Buridan, iki eşit miktarda yiyecek arasında açlıktan ölen eşeğin paradoksunu anlatır (Rescher, 1967). Her biri aynı ölçüde çekici iki seçenekle karşılaşan herkes ne yapacağını bilememe duygusunu yaşamıştır. Ama bunun bilgisayar devrelerinin ve yazılımının aynı kaynakları kullanmak zorunda kaldıklarında karşılaştıkları sorunları güvenilir bir biçimde çözümleme yetkisini sınırlayacak kadar temel bir mesele olduğu kimin aklına gelirdi?
Bilgisayar, seri olarak yeniden kullanılabilir kaynak taleplerinden birini seçen, bir seferde yalnız bir işlemci tarafından kullanılabilen seçici adlı devreler içerirler. Bellek bankaları, aritmetik fonksiyon birimleri ve iletişim kanalları gibi genel donanım araçları bu türden kaynaklardır. Özel dahili değişkenli alt-programlar ve data dosyaları gibi yazılımlar da bu türe girer. Bir seçici neredeyse eş zamanlı olan iki sinyal arasında bir seçme yapmak zorunda kalırsa ne olur? Talihsiz eşek gibi, seçici de başka devrelerce varsayılan süre içinde seçimini yapamazsa, sonuçlar her şeyi altüst edebilir. Seçme başarısızlıklarından biri, hiçbir işlemcinin devreye girmemesiyle bilgisayarın durmasıdır. Bir başkasında ise, birçok işlemci aynı anda devreye girerek ortak kaynakta tutarsızlığa, böylelikle de bütün sistemin iflasına (“crash”) yol açar.
Sorunu kısaca
özetleyelim:
N-girişli bir seçicinin N girdisi vardır (her işlemci için 1) ve tutarlı olarak tam çıktı durumuna sahip olması gerekir. Herhangi bir N girdisi için i durumu, i işlemcisinin seçildiğini ve ortak kaynağı kullandığını, 0 durumu ise hiçbir işlemcinin seçilmediğini ve kaynağın serbest olduğunu gösterir. Seçici 0 durumdayken i işlemcisi sinyal verirse, sinyal muhafaza edilir ve işlemci bekler. İşlemciler girdileri birbirinden ayrı zamanlarda verdiğinde seçicinin işlemini izlemek kolay olur. Sorun, iki işlemci taleplerini yaklaşık aynı anda bildirdiğinde başlar. Bu durumda seçicinin aynı anda, i ve j için ayrı ayrı, 0-i ve 0-j menzillerini izlemesi istenir. O zaman seçici, i ve j hedefleri arasında eşit ve tam bir dengede kalabilir. Kalıcı olmayan bu dengeye METASTABL DURUM adı verilir. Seçici metastabl durumda olduğu sürece, çıktı satırlarının bir anlamı yoktur. Çıktı devinimleri ya tam olarak iki tabanlı “0” ya da “1” olarak yorumlanamayacak ara değerler alırlar, ya iki ya da daha fazla seçmeyi işaret ederler, ya da arada salınırlar.
Metastabl durumlar, sabit durumlar arasındaki normal geçişlerde gidilip gelinen geçici durumlar gibi değildir. Metastabl durum süresiz devam eden bir denge noktasıdır. Buna karşılık geçici durum bir denge noktası değildir, süresi kısa ve sınırlıdır.
Süresi, seçicinin girdileriyle metastabl durumun ne kadar yakınına getirildiğine ve geçiş hızına bağlıdır. Bu durum bir kayanın tepesinde hareketsiz duran topunkine benzer. Topun kayadan düşüp yerde durma noktasına gelmesi kayanın tepesinde ne kadar iyi dengelendiğine ve kayanın eğimine bağlıdır. Nasıl topun kayanın üstünde ne kadar kalacağı tam olarak bilinemezse, seçicinin metastabl durumunun ne kadar süreceği de tam olarak bilinmez. Seçme başarısızlığını önlemenin yolu yok mudur? Kolayca akla gelen: Evet, her şey ortak bir saate bağlanıp, sinyallerin çıkarıldığı ve kullanıldığı anlar ayrı saatlere bölüştürülür. O zaman, seçici devreler yalnızca sinyal yollayan devrelerin gönderdiği değişmez sinyalleri görür. Bu hipotezin yürümeyen yanı bazı sinyaller geldiğinde kontrolün olanaksızlaşmasıdır. Örneğin bir dosya aktarımının sonunu bildiren kesme sinyali tam olarak kontrol edilemez, çünkü diskin dönme süresi bütünüyle kontrol edilemez. Birlikte gelen iki sinyalden hiç değilse biri tam olarak kontrol edilemiyorsa, çakışma anında seçme başarısızlığı ortaya çıkabilir. O zaman sürekli çalışan bir saatle seçme sorunu çözümleniyor demektir. Peki saat durdurulabilirse ne olur? Cambridge Üniversitesi Bilgisayar Laboratuvarı'ndan David Wheeler, Cambridge CAP Bilgisayarı için bir seçici tasarladı. Wheeler'ın seçicisi, sabit bir durum sokulduğunda bunu saptayıp özel bir çıktı hazırlayan ek bir eşlik devresi içerir. Tasarıya göre, eşlik eden devreler bir seçme olayının başlatılmasından hemen sonra saati durdurur; özel bir çıktının seçmenin gerçekleştirildiğini bildirmesiyle seçme devresi saati yeniden çalıştırır. Bu durumda seçme başarısızlığı mümkün değildir. Ancak bunun da riski vardır: Özel çıktının hazırlanmasının ne kadar zaman alacağı önceden kestirilemez. Bu çıktının hazırlanıp saatin tekrar çalıştırılmaya başlaması normalde çok az bir zaman alır. Ancak, birkaç kararın alınması bazı sistemlerin kaldırma gücünü aşacak kadar uzun gelebilir. Seitz, ayrıca saati bulunmayan, kendinden zamanlamalı devreler adı verilen bir devre türünü de betimler. Kendinden zamanlamalı devrelerin elemanları taleplerin ve kabul edilmiş sinyallerin alınıp verilmesiyle birbirini harekete geçirir: Her eleman ancak önceki talebin alınmasından sonra yeni bir talep öne sürer. Bunlar iç bağlantı adını alan ve Wheeler'ın devresine benzeyen eleman seçme işinde kullanılır. İç bağlantı bir karar verinceye dek beklemek zorundadır. Elemanlar arası sinyal alışverişinde saatli devrelerden daha fazla enerji harcandığından kendinden zamanlamalı devreler yüksek performanslı bilgisayar için pek elverişli değildir. Ancak daha emniyetli oluşları, paralel bilgisayarlarda kullanımlarını gitgide daha çekici kılmaktadır. Seçiciler ve iç bağlantılar aynı zamanda “karşılıklı dışlama” devreleri adını da alırlar. Saatle ölçülmeyen girdilerle iç saatin eşleştirilmesinde kullanılan devrelere örnektirler. Girdilerin saatle aynı anda değişmesini idare edebilmek için eşleştiricilerde seçicilerin bulunması gerekir. Bu nedenle, seçme başarısızlığı aynı zamanda eşleştirme başarısızlığı adını da alır.