Arnold I. Durney

Hızlı Rastgele Erişimli Bellek Sistemleri için İndeksleme

Arnold I. Durney
Roslyn Heights, N.Y.

Piyasada bulunan veya geliştirilmekte olan bir dizi bellek aygıtı aşağıdaki özelliklere sahiptir:

1. Bir depolama birimi, örneğin 50.000 ile bir milyon arasında, çok sayıda adreslenebilir konum içerir.
2. Her konum 50 ile 200 karakter arasında veri saklar.
3. Bir konuma erişim süresi küçüktür; birkaç yüz milisaniyeden birkaç saniyeye kadar değişir.
4. Erişim süresi küçük sınırlar içinde değişir; yani okuma aygıtının mevcut durumu, onu bir sonraki konumuna getirmek için gereken süreyi etkilemez.
5. Okuma süresi görece hızlıdır.
6. Belleğe yapılan çağrıların önceden sıralanması gerekmez; rastgele sırayla gelirler. Bu çağrıların rastgeleliği, “rastgele erişimli bellek” teriminin kullanılmasına yol açmıştır.

Bu türün kamuoyuna duyurulmuş bazı mekanizmaları şunlardır: Telecomputing Corporation’ın Mass (Multiple Access Storage System) sistemi, Potter Instrument Company’nin Ram sistemi, IBM’in Ramac 650 ve 305 “jukebox” sistemleri ve LFE’nin yüksek yoğunluklu manyetik tamburu.

Birçok durumda bu tür aygıtlar, oldukları gibi kullanışlıdır. Örneğin, bir envanterdeki kalemler 00001’den 50.000’e kadar numaralandırılmış olabilir. 37415’e karşılık gelen adreslenebilir konumda, bu numaraya sahip kalemle ilgili yararlı bilgileri saklayabiliriz. Bu bilgiler, maliyeti, eldeki miktarı, yeniden sipariş noktası, depo konumu vb. olabilir. Bilgi bulmak istediğimiz şeyin adı olan bu kalem numarasına kalem tanımı diyelim. Dosyada bulunan ve görmek istediğimiz bilgilere ise saklanan bilgi ya da kısaca bilgi adını verelim.

Son olarak tanımlanan türdeki kalem tanımları kontrollüdür; yani dosyalama sistemini işleten kuruluş tarafından atanmışlardır. Bu kontrol sayesinde bellek kullanıcısı, bir kaleme ilişkin bilginin bellekte nerede saklandığını bulma zahmetinden kurtulur. Böylece, birkaç bin çalışanı olan bir işveren, zaman saati numaralarını 1 ile 10.000 aralığında tutacak şekilde kontrol edebilir. Bir telefon şirketi, abonenin telefon numarası verildiğinde adını ve adresini bulmak için kullanılan ters telefon rehberlerini tutarak telefon rehberlerini kontrol edebilir.

Kontrollü türdeki durumlar, rastgele erişimli bellekler için adeta özel olarak uygundur. Ancak uygulamada karşılaşılan durumların azınlığını temsil ederler.

Daha yaygın olarak, bir parça numarası veya katalog numarası, bazen bir tanımı ima eden, bazen de uzun ve artık güncelliğini yitirmiş tarihsel bir sürecin sonucu olan, rakam ve harflerden oluşan uzun bir dizidir. Örneğin, toplamda yaklaşık 60.000 satır kalemi içeren bir parça envanteri vardır ve bu envanterde parça numaraları 15’e kadar rakam ve harften oluşmaktadır. Başka bir deyişle, 10¹⁵’ten fazla olası kümeden yalnızca 60.000 kalem tanımı kullanılmaktadır. Bir telefon rehberi kaydındaki ad ve adres bölümü yaklaşık 30 karakterden oluşur. 30 karakter uzunluğundaki tüm olası dizileri (bir karakterin harf, rakam veya boşluk olabildiği durumda) dikkate alırsak, 37³⁰ adet böyle dizi vardır. Kontrollü kalem tanımı belleği gibi çalışacak bir bellek, içinde 37³⁰ adreslenebilir konum bulundurmak zorunda kalırdı. Bu aşırı bir büyümedir. Kontrolsüz kalem tanımlarını rastgele erişimli bir bellekte ve bunu ekonomik biçimde yapabilmek istiyoruz.

İndeksleme

Dikkate alabileceğimiz ya da almak zorunda olduğumuz pratik sınırlar şunlardır:

1. Bellekteki konum sayısı.
2. Her birinin karakter veya bit cinsinden kapasitesi.
3. Belleğin geometrisi; yani bir adres ikili bir sayı mı, ondalık mı, yoksa başka bir şey mi?
4. Saklamayı beklediğimiz kalem sayısı.
5. Her bir kalemin karakter veya bit cinsinden boyutu.
6. Bazen günlük iş yükü ve bir kalemi işlemek için gereken süre önemlidir; ancak bu nokta burada ele alınmayacaktır.
7. Her kalem için her şeyi saklamak zorunda olup olmadığımız; yoksa bazı kalemleri dışarıda bırakıp bırakamayacağımız, ya da kalemlere ait bilginin yalnızca bir kısmını saklayıp saklayamayacağımız veya her ikisi.
8. Kalemlerin “ölümlülüğü”: listenin hiç değişmediği mi, az değiştiği mi, yoksa kalemlerin sürekli eklenip çıkarıldığı bir liste mi olduğu.
9. Bir kalemi bulmak için birden fazla konuma gidebilip gidemeyeceğimiz.
10. Kalem tanımının niteliği; yani boyut dağılımı vb.

Yukarıdakilerin tüm kombinasyonlarını kapsayan basit bir kural olmamakla birlikte, uygulanabilir bir çözüm neredeyse her zaman mümkündür.

Örneğin Yirmi Soru oyununu ele alalım. Liste ölümlülüğünün olmadığı durumlarda büyük bir depolama tamburu aşağıdaki şekilde etkili biçimde kullanılabilir. Saklanan kalemler önce sıralanır. Her biri M kalem alabilen N adet tambur izi varsa, ilk M kalem iz 1’e, ikinci M kalem iz 2’ye vb. yüklenir. Arama sırasında orta iz incelenir. Oradaki kalemler, sıralama ilişkisine göre, aranan kalemden daha yüksekse, orta iz ile iz 1 arasındaki orta noktadaki ize gidilir. Orta izdeki kalemler daha düşükse, orta iz ile iz N arasındaki orta noktadaki ize gidilir. İkinci turda, incelenecek ikinci izin bulunduğu tamburun o yarısı içinde işlem tekrarlanır. Üçüncü turda arama tamburun dörtte birine daraltılır ve bu şekilde devam eder. En kötü durumda, yukarı yuvarlanmış log₂ N kadar iz incelenmesi gerekir. Aranacak iz sayısının beklenen değeri (log₂ N) − 1’dir.

Bu yöntemin bir varyantında, iz n üzerindeki her kalemin, sıralama ilişkisine göre, (n − 1) numaralı izdeki her kalem için bir üst sınır olması yeterlidir. Bir iz içindeki kalemlerin sıralı olması gerekmez. Bu yöntemde, her biri farklı bir iz üzerinde bulunan (log₂ N − 2) adet tekil kalemin incelenmesi gerekir; buna ek olarak iki tam iz incelenir. Hızlı kafa anahtarlaması ve büyük M değerleri ile bu yöntem önemli bir zaman tasarrufu sağlar. Ayrıca, bir iz içindeki sıralamanın gevşetilmesi, her birinin bir kısmının boş bırakılmasına izin verir; böylece bazı silmeler ve eklemeler (ölümlülük) mümkün olur.

Yöntem, yukarıdaki Yirmi Soru örneğinde olduğu gibi, önce orta izi incelemektir. Ancak bu kez, iz üzerindeki yalnızca bir kalem tanımı, aranan kalem tanımı ile karşılaştırılır. Saklanan kalem tanımı daha yüksekse, alt yarının alt orta izine geçilir. Yine bir kalem tanımı incelenir. İki olasılık vardır:

1. Saklanan her iki kalem tanımı da daha yüksektir. Bu durumda, yeni bir üst sınır bulduğumuz için orta iz kesinlikle değerlendirme dışı bırakılabilir.
2. Yeni kalem tanımı daha düşüktür. Bu durumda orta iz ile ikinci iz arasındaki orta noktadaki ize geçersek, önceki paragrafta ortaya konan benzer bir akıl yürütme ile ikisinden biri elenecektir.

Bu sürecin sürdürülmesi sonunda bizi bitişik iki ize indirger. Kalem bu ikisinden birinde bulunduğundan, bu iki iz bütünüyle incelenmelidir. Hızlı anahtarlama ile kalemi bulmak için geçen süre, Yirmi Soru yöntemine kıyasla belirgin biçimde daha kısadır. Kalem tanımının ara karşılaştırmalardan birinde bulunma olasılığı göz ardı edilmiştir; çünkü bu ikinci dereceden bir olasılıktır.

Bu iki durumda da, kalemi, adresini önceden bulmadan elde etmiş olduk.

Büyük tambur varsayımını sürdürerek, tamburlar için iki adres bulma şeması aşağıda verilmiştir.

Birincisinde, her depolama izine sıralama düzeninde bir üst sınır atanır. Herhangi bir iz için bu sınır, bir sonraki izdeki herhangi bir kalemden daha düşüktür. Kalemlerin sıralama ölçeği boyunca dağılımının eşit olmadığı biliniyorsa, bu sınırların eşit aralıklı olması gerekmez.

Bir adres izleri kümesi üzerinde, bu tür her üst sınır sırayla kaydedilir ve muhtemelen ilişkili izin numarası da kayda geçirilir. Arama sırasında önce adres izleri taranır. İz konumunu belirtme yöntemine bağlı olarak, eşya numarasına eşit olan ya da onu aşan bir üst sınır numarası okunur okunmaz, iz adresi ya yukarı doğru sayılarak ya da doğrudan okuma yoluyla bulunur.

İkinci yöntemde, her bir eşya depolamaya kaydedilirken, tam konumu da adres izlerine kaydedilir. Önce adres izlerinde konum aranır. Bu yöntem, sıralama ölçeği boyunca dağılımın son derece değişken olduğu, mortalitenin yüksek olduğu ve eşyadaki karakter sayısının, eşya tanımındaki karakter sayısına kıyasla büyük olduğu durumlarda yararlı olacaktır.

Yukarıdaki yöntemlerin tümü, bellek aygıtını bağladıktan sonra anahtarlama, karşılaştırma veya hesaplama açısından oldukça fazla iş yapmamızı gerektirir. Belleğe gitmeden önce eşya tanımı üzerinde yapabileceğimiz bir şey varsa, bundan daha iyi sonuç alabiliriz.

Kolaylık olması için, adreslenebilir bellek konumlarının sayısının 100.000 olduğunu, 50.000 adet eşya tanımına (adlar ve adresler, parça numaraları veya benzerleri) sahip olduğumuzu ve eşya tanımının çok uzun olduğunu, 30 alfasayısal karaktere kadar çıkabildiğini varsayalım (boşluk veya yedek dahil 37 olası karakter). Ayrıca eşya mortalitesini de varsayalım.

37³⁰ olası eşya tanımı vardır. Elbette bu 37³⁰ kümesinin başka bir 100.000’lik kümeye bire bir eşlenmesi yoktur. Ancak olası tanımlar kümesinden yalnızca 50.000 tanım kullanıyoruz. Bu bize yardımcı olabilir mi?

Bazen yanıt evettir; yazarın deneyimlerinden bir örnek bunu gösterecektir. Belirli bir imalat şirketinin, binlerce kalemden oluşan bir parça ve montaj listesi vardı. Eşyaları numaralandırmak için altı basamaklı, sayısal ve alfabetik karışık bir sistem kullanılıyordu. Kamuya sekiz adet karmaşık makine veya montaj satılıyordu. Bunların eşya numaraları genel sistemden alınmıştı. Bu sekiz eşya için bir delikli kart kontrol sistemi kurulurken, başlangıçta her eşya için altı basamaklı numaranın tamamının kaydedilmesi önerildi. Ancak sekiz montaj numarasının incelenmesi, dördüncü basamakta hiçbir ikisinin aynı olmadığını ortaya koydu. Dolayısıyla sıralama amaçları için yalnızca dördüncü basamağın kaydedilmesi yeterliydi; böylece diğer amaçlar için son derece gerekli olan beş bilgi alanı serbest bırakılmış oldu.

Eşya tanımının incelenmesi, alanı pratik bir boyuta indirmek için kullanılabilecek yerleşik bir fazlalığı ortaya çıkarabilir.

Genellikle bu kadar şanslı olmayız. Bununla birlikte, bellek konumlarının benzersiz atanması umudundan vazgeçip, pratik ya da istatistiksel kabul edilebilirlik lehine bir yaklaşım benimseyebiliriz. Örneğin, eşya tanımlarının incelenmesi, karakter konumlarının bir alt kümesinin rastgele dağıldığını ortaya koyabilir. Diyelim ki 15 basamaklı bir parça numarasının ortadaki beş basamağının rastgele dağıldığı bulunmuş olsun. Bu tür incelemelerin, sıradan veri işleme teknikleriyle yapılmasının oldukça kolay olduğunu belirtmek gerekir. Bu beş basamağı, 100.000 konumlu belleğimiz için eşya tanımı olarak kullanmaya karar verelim. 50.000 eşya bulunduğuna göre, aşağıdaki durumla karşı karşıyayız:

1. Belirli bir konumun dolma olasılığı 1/2’dir.
2. Her bir konum için beklenen değer 0,5 eşyadır.
3. Eşyalar genel olarak Poisson dağılımına göre dağılacaktır.

4. Her konum yalnızca bir eşya tutuyorsa, adresleme düzeni altında yinelenenler için yer olmayacaktır.

5. maddeyle bir şekilde başa çıkmamız gerekir. Bunun için birkaç yöntem vardır:

6. İstisna yoluyla. Yinelenmelerin olduğu durumlarda yalnızca en popüler eşyayı depolayın (stoklar genellikle parçaları hızlı veya yavaş olarak sınıflandırır). Taşan eşyaları başka bir yolla ya da elle arayın. Bu yöntemin ne kadar sık işe yaradığı şaşırtıcıdır.

7. Belleği yeniden düzenleme. Örneğin:

8. a. Yalnızca tek numaralı adresler kullanılırsa,
9. b. Adreslenen bir konum ve onun yanındaki konum (örneğin 01921 ve 01922) her zaman birlikte incelenirse,
10. c. Beş basamaklı türetilmiş parça numaralarımız tek sayılıymış gibi ele alınırsa.

Böylece 17424 parça numarası 17423 olur. Sonuçta 50.000 eşya 50.000 adrese gider. Ancak artık her adresin iki eşya kapasitesi vardır ve beklenen değer birdir. Taşma sayısı belirgin biçimde azalacaktır.

1. Adresleme düzenini ayarlama, daha sonra açıklanacak bir yönteme göre, doğrudan adreslerin sayısını azaltmak ve fazla konumları taşmaları depolamak için kullanmak. Taşma adresini, depolanan eşya bilgisinin sonuna ekleyin. En iyi azaltma oranının ne olduğu duruma göre değişir. Bu yöntemler kullanıldığında yapılacak erişim sayısının beklentisinin arttığını unutmayın. Genellikle her erişimde, tam eşya tanımını kullanarak kontrol yaparız.

2. Birleşimler. Yukarıdakilerin bazı birleşimleri mümkündür ve donanıma ve probleme bağlı olarak bazen hatta gerekli olabilir. Unutmayın ki adresleme düzeni bizi yalnızca bir bellek konumuna götürür. Normalde bellekte doğru eşyayla çalıştığımızdan emin olmak için eşya tanımının tamamına ihtiyaç vardır.

Zorluk ölçeğinde en kötü durum, tanımın çok sayıda karakter konumu kullandığı, mortalitenin yüksek olduğu ve parça numarası örneğinde olduğu gibi üzerinde çalışabileceğimiz iyi bir konum alt kümesi bulamadığımız durumdur. İşte bu problemle başa çıkmanın iki yolu.

1. Karakter konumları kümesinin bağımsız olarak değiştiği, ancak her bir konumun düzgün dağılmadığı ortaya çıkabilir. Diyelim ki bir sütunda K olası farklı karakter var ve bunlardan en sık görüleni zamanın %25’inde ortaya çıkıyor. Birleşik frekansı %25’e eşit olan karakter alt kümeleri toplanabiliyorsa, K yerine dört kategori elde ederiz ve en azından o sütun için tabanımızı K’dan 4’e düşürmüş oluruz. Bu tekniğin, yukarıda açıklanan seçim ve diğer yöntemlerle birleştirilmesi, tanımlayıcı popülasyonumuzu belleğe sığacak noktaya kadar azaltabilir. Bunun, karakter bağımsızlığı kısıtı altında bir rastgeleleştirme tekniği olduğu açıktır. Ayrıca, karakter sayısının asal olmadığı düzgün dağılımlar için de yöntemin geçerli olduğu açıktır. Vurgulanmalıdır ki yaptığımız tek şey, adreslenebilir bellek depolama konumlarının sayısına uyacak şekilde olası eşya tanımlarının sayısını azaltmaktır. Bunun bedeli, kontrollü bir durumda sahip olduğumuz türden benzersiz depolama konumu atamalarına artık sahip olmamamızdır. Ancak eşya tanımlarının rastgele bir dağılımıyla sonuçlandıysak, problemi taşmalarla ilgilenme sorununa indirgemiş oluruz ve bu sorunu tatmin edici biçimde çözmenin yollarını açıklamış bulunuyoruz.

2. Eşya tanımını, 37 tabanında ya da her neyse o ölçekte bir sayıymış gibi ele alın. Ya da uygun delikli şerit kodlamasını kullanarak ikili bir sayı olarak yazın. Bu sayıyı, adreslenebilir konum sayısından biraz daha küçük bir sayıya bölün (yazar en yakın asal sayıyı tercih eder). Bölümü atın. Kalanı adres olarak kullanın; duruma göre taban 10’a ayarlama yapın.

3. Yeterince iyi olan başka dönüşümler de vardır. Hangisinin kullanılacağı, ilişkili hesaplama donanımının niteliğine ve eldeki özel problemin diğer özelliklerine bağlıdır.

Birçok diğer veri işleme problemi gibi, dönüşümler problemi de yalnızca temel noktaların kısa bir taslağıyla ortadan kaldırılamaz. Bir çözümün uygulanabilirliği değerlendirilirken, girdi hazırlığı, bilginin farklı dosyalar arasında dağıtılması ve bazen de işlemsel reformlar ya da değişiklikler dahil olmak üzere pek çok ilişkili problem tartılmalıdır. Ancak en azından kullanabileceğimiz tekniklerden tamamen yoksun değiliz.