Geri Dön

A new algorithm for reordering buffer management problem and experimental evaluations in discrete distributions

Arabellek ile yeniden sıralama problemi için yeni bir algoritma ve ayrık dağılımlarda yapılan deneylerin sonuçları

PDF İndir

  1. Tez No: 676172
  2. Yazar: GÖZDE FİLİZ
  3. Danışmanlar: PROF. DR. MUHAMMED OĞUZHAN KÜLEKCİ
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Sezgisel algoritmalar, Yeniden zamanlama, Heuristic algorithms, Rescheduling
  7. Yıl: 2021
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Lisansüstü Eğitim Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Bilimleri Ana Bilim Dalı
  12. Bilim Dalı: Bilgisayar Bilimleri Bilim Dalı
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

Yeniden sıralama problemleri ekonomiden bilgisayar sistemlerine kadar geniş bir yelpazede doğal olarak ortaya çıkar ve önemli bir rol oynar. Yeniden sıralama probleminde, görevler ya da işlemler bazı öncelik kısıtlamaları dikkate alınarak belirli bir kaynağa atanmaktadır. Görevlerin belli bir süreliğine geciktirilebildiği bazı uygulamalarda arabellekler önemli bir rol oynar. Arabellekler, bazı görevleri geçici olarak depolayarak, görevlerin kaynağa girişine öncelik kısıtlamaları lehine izin vermek içi kullanılabilir. Bu nedenle, arabellek yönetimi yeniden sıralama problemlerinde belirleyici bir role sahiptir. Sabit disklerde, dönen yüzeyin üzerinde bir okuma/yazma kafası mevcuttur ve bu kafanın konumu disk içerisinde hangi silindire erişilebileceğini belirler. Kafanın silindir üzerindeki hareketi zaman alır ve bu zaman sabit diskin performansını belirler. Erişimlerin hedef silindirlerin pozisyonuna göre yeniden sıralanması için arabellek kullanılması, erişim zamanını azaltabilir. Bilgisayar grafiklerinde görselleştirme yapılırken çizim temel öğeleri kullanılır. Görselleştirme sisteminin performansı, çizim temel öğelerinde gerçekleşen durum değişiklerine bağlıdır. Durum değişiklikleri iki ardışık temel çizim öğesi arasında doku, renk veya gölge farklılıkları olduğunda meydana gelir. Görselleştirme sırasında karşılaşılan durum değişikleri sistemde gecikme yaratır, bu nedenle benzer özniteliklere sahip temel çizim öğelerinin arka arkaya işleme alınması sistem için faydalı olacaktır. Arabellek gelen temel çizim öğelerini özniteliklerine göre yeniden sıralamak için kullanılabilir. Ağ iletişim sistemlerinde, iki ardışık paketin farklı düğümlere gönderilmesi bir maliyet oluşturur. Bu nedenle sunucunun aynı düğüme gönderilecek paketleri bir arada göndermesi sitem için faydalıdır. Arabellek paketlerin uygun şekilde yeniden sıralanması için kullanılabilir. Otomotiv endüstrisindeki boyama atölyelerinde, otomobil gövdeleri, her otomobil gövdesinin kendi son kat boyası ile boyandığı bir son kat boyamadan geçmektedir. Birbirini izleyen iki arabanın farklı renklerde boyanması gerekiyorsa, renk değişikliği gerekir, bu da bir temizlik ve kurulum maliyetine neden olur. Bu maliyet arabellek kullanılarak yapılan bir yeniden sıralama ile azaltılabilir. Arabellek ile yeniden sıralama probleminde, belirli bir öznitelikle karakterize edilen n öğeden oluşan bir girdi dizi bulunmaktadır. Anlatımı sadeleştirmek adına bu özelliği öğenin rengi olarak adlandıracağız. Girdi dizisindeki tüm öğeler bir servis istasyonu tarafından işlenmek üzere sırada beklemektedir. Öğelere renklerine göre servis istasyonu tarafından farklı işlemler uygulanacaktır. Uygulanacak işleme göre servis istasyonundaki sürecin değiştirilmesi maliyet oluşturmaktadır. Dolayısıyla, farklı renklere sahip her bir ardışık öge çifti için bir maliyet oluşur. Maliyeti en aza indirmek için içerisinde k öge barındırabilen bir arabelleğe sahibiz. Sırada bekleyen öğeler önce arabelleğe giriş yapar. Arabellek dolduğunda, arabellek ile yeniden sıralama algoritması bir çıktı rengi seçer ve arabellekte bu renge sahip olan tüm öğeler servis istasyonuna iletilir. Öğeler servis istasyonu tarafından işlendikten sonra çıktı dizisine eklenir. Arabellekteki boş pozisyonlar sırada bekleyen öğelerle tekrar doldurulur. Bu mekanizma girdi dizisindeki tüm öğeler işlenene kadar devam eder. Tüm algoritmalar boş bir arabellekle başlar ve biter. Arabellekte son seçilmiş çıktı rengine sahip bir öge varsa algoritma kararında bir değişiklik yapmaz. Ayrıca, arabellekte boş bir pozisyon varsa, algoritma arabellekten herhangi bir öğeyi servis istasyonuna iletmez. Arabellek ile yeniden sıralama problem, problemin bileşenlerine göre sınıflandırılabilir. Problemin tanımlayıcı özelliklerinden birisi maliyet fonksiyonudur. Maliyetin tek tip olduğu durumda, herhangi bir renkten diğerine geçerken aynı maliyet oluşur. Bu nedenle maliyet çıktı dizisindeki öznitelik değişikliklerinin sayısı olarak ölçülebilir. Maliyetin tek tip olmadığı durumda ise, bir renkten diğerine geçerken farklı maliyetler ortaya çıkabilir. Problemin çevrimiçi varyantında, algoritma gelecekte arabelleğe ulaşacak öğeler hakkında bilgi sahibi değildir. Diğer bir deyişle, girdi dizisi önceden bilinmemektedir ve algoritma yalnızca arabellekte bulunan öğeleri dikkate alarak karar vermek zorundadır. Öte yandan problemin çevrimdışı varyantında, algoritma girdi dizisini tamamını dikkate alarak karar verebilir. Problemin maksimizasyon varyantında, amaç çıktı dizisindeki öznitelik değişliklerini en aza indirmek yerine, girdi dizisinde elenen maliyet sayısını en üst düzeye çıkarmak olarak tanımlanmıştır. Bu tez çalışmasında, arabellek ile yeniden sıralama probleminin çevrimdışı varyantında ideal çözüm için gerekli olan en az tampon büyüklüğünü kanıtladık. Renk seçiminin her zaman arabellek dolu olduğunda yapıldığı ve algoritmanın arabellekte en çok bulunan rengi çıktı rengi olarak seçtiği varsayımıyla, o_1<2∙⌈k/σ⌉ veya o_2<⌈k/σ⌉ eşitsizliğini sağlayan en küçük arabellek büyüklüğü k bize ideal çözümü garanti etmektedir. Tanımlamada o_1 ve o_2 sırasıyla girdi dizisinde en sık görülen ve ikinci en sık görülen renklerin frekansını, σ ise girdi dizisinde görülen farklı renklerin toplam sayısını ifade etmektedir. Çalışmamızın devamında bu kanıtın sonuçlarını kullanarak problemin çevrimiçim varyantı için buluşsal bir algoritma önerdik. Minimum arabellek büyüklüğü ile ilgili kanıtımız girdi dizisine ilişkin en sık görülen ve ikinci en sık görülen renklerin frekansı ve girdi dizisinin renk uzayının büyüklüğü bilgilerine sahip olmayı gerektirmektedir. Oysa problemin çevrimiçi varyantında bu bilgilere sahip değiliz. Algoritmamız çıktı renginin seçilmesi sırasında arabellekte mevcut bulunan girdi dizisinin alt dizisine ilişkin bilgiyi kullanır. Böylece mevcut durumda incelenmekte olan bu alt dizi için arabellek büyüklüğünün ideal olup olmadığında bakar. Arabellek boyutu bu alt dizi için ideal olmadığında, algoritma ilk çalıştırmada girdi dizisindeki bazı öğelerin atlanmasına izin veren bir rahatlama tekniği kullanmaktadır. Bu rahatlama bize bir şekilde sırada bekleyen bir sonraki öğeyi seçmek yerine daha fazla öğeyi gözlemleme şansı verir. Bu seçilim işlemi sebebiyle algoritmamızı Titiz algoritma olarak adlandırdık. Titiz algoritmanın ana fikri, girdi dizisinin alt dizileri için ideal çözümü garanti etmektir. Algoritma arabellek büyüklüğü gözlemlenen alt dizi için ideal olduğu sürece arabellekte en sık görülen rengi çıktı rengi olarak seçer ve arabellekten çıkarır. Kanıttaki eşitsizlik ihlal edildiğinde yani arabellek boyutu alt dizi için ideal olmadığında, algoritma arabelleğin renk uzayı büyüklüğünü küçülterek arabelleği ideal hale getirmeye çalışır. Arabellekte en az bulunan renge ait bir öğeyi daha sonra tekrar işlenmek üzere sıradan çıkarır ve sıranın sonuna ekler. Sırada bekleyen yeni bir öğeyi arabelleğe alır ve arabellek boyutu ideal hale gelene kadar bu işlemi tekrarlar. Bu süreç, bazı öğelerin ilk çalıştırmada atlanmasına izin veren ve tüm girdi dizisi ilk kez işlendikten sonra tekrar işlenebilmelerini sağlayan bir rahatlamadır. Ayrıca arabelleğin araştırma aralığını genişletmenin bir yolu olarak da tanımlanabilir. Bazı öğelerin çıktı dizisine değil de girdi dizisinin sonuna eklenmek üzere arabellekten çıkarılabilmesi, algoritmamızın mevcut duruma uygun olan öğeleri girdi dizisinden seçmesini sağlamaktadır. Bu seçilim işlemi sayesinde arabellek boyutunun çıktı rengi seçilimi sırasında girdi dizisinin alt dizisi için ideal olduğunu garanti edebiliyoruz. Ayrıca seçilim işlemi ile aynı anda arabellekte bulunmayan bazı öğelerin daha sonraki çalıştırmada arabellekte birlikte bulunması da mümkün olabilir. Tez çalışmamızın bir diğer önemli sonucu belirli ayrık dağılımlarda tek tip maliyet fonksiyonuna sahip arabellek ile yeniden sıralama probleminin çevrimiçi varyantına ilişkin yapılan ilk deneysel değerlendirme sonuçlarıdır. Tekdüze, Binom, Negatif Binom, Geometrik, Poisson ve Zipf dağılımlarını takip eden 1.000, 5.000 ve 10.000 uzunluğunda veri setleri oluşturduk. Her girdi dizisi uzunluğu için 10, 20 ve 50 renk uzayı büyüklüğüne sahip versiyonlar oluşturduk. Her bir dağılım, girdi dizisi uzunluğu ve renk uzayı büyüklüğü için 50 adet rastgele veri seti oluşturduk. Bu veri setlerinde Bounded Waste (Sınırlandırılmış İsraf), Random Choice (Rastgele Seçilim) ve Titiz algoritmalarının girdi uzunluğunun %1'i, %2'si ve %5'i uzunluğundaki arabellek uzunlukları ile çalıştırdık. Her bir veri setinin girdi dizisi uzunluğu, renk uzayı büyüklüğü, dağılım ve dağılım parametresi olmak üzere 4 değişkeni bulunmaktadır. Bu değişkenlerden 144 adet farklı veri seti oluşturduk, her değişik veri seti için 50 rastgele dizi oluşturarak veri seti sayımızı 7.200'e yükselttik. Her bir testin ise veri seti, algoritma ve arabellek uzunluğu olmak üzere 6 değişkeni bulunmaktadır. Bu değişkenlerle 64.800 farklı test sayısına ulaştık. Bu da her bir algoritma için 21.600 test yapıldığı anlamına gelmektedir. Algoritmaların performansını ölçmek için Çıktı/Girdi Dizisindeki Değişim Oranını tanımladık. Bir dizideki değişim iki ardışık öge arasında meydana gelen bir renk değişikliğini ifade etmektedir. 432 değişik veri seti ve arabellek uzunluğu için oluşturulmuş 50 rastgele diziden algoritmaların Çıktı/Girdi Dizisindeki Değişim Oranlarının ortalamasını sonuç olarak aldık. Veri setlerini oluşturmak ve algoritmaları çalıştırmak için Python 3 kullandık. Her bir ayrık dağılım için algoritmaların performans sonuçlarına çalışma içerisinde detaylı olarak yer verdik. Titiz algoritma 432 vakadan 409'unda (%95) en iyi performansı gösterdi.

Özet (Çeviri)

Scheduling problems emerge naturally in a broad range of application areas from economics to computer systems. In the scheduling problem, tasks or activities must be assigned to a given resource while satisfying some precedence constraints. For some applications in which tasks can be ignored for a period of time, buffers can be used to store the delayed items temporarily to permute the input of tasks. In these applications, buffer management strategies play an important role. In the reordering buffer management problem, we have an input sequence of n items which are characterized by a particular attribute, which we will refer to as color, and a buffer of size k. A cost occurs when serving a pair of consecutive items with different colors. A reordering buffer management algorithm aims to permute the input sequence using the buffer to minimize the total cost. In this thesis, we proved the minimum buffer length for the optimal solution to the reordering buffer management problem in the offline setting. With the assumption that color selection is always made when the buffer is full, selecting the most frequent color from buffer given the smallest buffer size k that satisfies either o_1<2∙⌈k/σ⌉ or o_2<⌈k/σ⌉ guarantees the optimal solution, where o_1 and o_2 represent respectively the frequency of the most and the second most frequent colors in the input sequence X, and σ is the number of distinct colors appearing in X. Additionally, we proposed a new algorithm using the proved observation as a heuristic for the online setting of the problem. The observation of the minimum buffer length requires the knowledge of the color size and frequency of the most and second most frequent color of the input sequence. However, in the online setting, we do not have this information. Our algorithm uses the limited information of buffer to decide whether buffer size is optimal for the sub-sequence of the input sequence that is inspected by buffer at the stage of selecting output color. When the buffer size is not optimal, the algorithm uses a relaxation in which some items can be skipped in the first run. In a way that, we are not forced to select the next item waiting on the queue, but we have the chance to observe more items. By means of this picking process, we refer to the algorithm as Picky algorithm. Another significant outcome of the thesis is the results of the first experimental evaluation setup for the online version of the reordering buffer management problem with uniform cost function on specific discrete distributions. We have used Uniform, Binomial, Negative Binomial, Geometric, Poisson, and Zipf distributions to generate input sequences of sizes 1.000, 5.000, and 10.000 with color sizes 1%, 2%, and 5% for each one. Each item in the input sequence is assigned a color in the color range as 0,1, 2…. For all distributions, input sizes, and color sizes, we have generated 50 random data sets. After, we have implemented Bounded Waste, Random Choice, and Picky algorithms to the data sets with buffer sizes %1, %2, and %5 of the input size. Each data set has 4 variables as: input size, color size, distribution and distribution parameter if exists. We have 144 different combinations from the variables and 50 random data sets for each combination, that means we have generated 7.200 data sets. Each experiment has 6 variables as input size, color size, algorithm, buffer size, distribution, and distribution parameter if exists. We have 1.296 different combinations from these variables and with 50 random data sets for every input size, thus we have conducted 64.800 different experiments, 21.600 experiments per algorithm, and evaluated the performance of the algorithms according to the cost diminished. To assess the algorithms' performance, we have used the Output/Input Switch Ratio where a switch is defined as a color change that occurs between two consecutive items in the sequence. For every 432 different data sets and buffer size pair, we have taken the average of the Output/Input Switch Ratio from the 50 data sets as the final result. We have used Python 3 to generate the data sets and implement the algorithms. For each discrete distribution, we have presented detailed results for each data set combination and compare the performance. Out of 432 different combination data sets and buffer size pairs, Picky algorithm showed the best performance in 409 cases which is approximately %95 of all cases.

Benzer Tezler

  1. Tez No

    397890

    Leon3 mikroişlemcisi tabanlı sistem tasarımı

    Leon3 microprocessor based system design

    AHMET ÇAĞRI BAĞBABA

    Yüksek Lisans

    Türkçe

    Türkçe

    2015

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    DOÇ. SIDDIKA BERNA ÖRS YALÇIN

  2. Tez No

    58591

    Pararllel rendering algorithms for distributed-memory multicomputers

    Çok işlemcili dağıtık hafızalı bilgisayarlarda paralel görüntüleme algoritmaları

    TAHSİN MERTEFE KURÇ

    Doktora

    İngilizce

    İngilizce

    1997

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. CEVDET AYKANAT

  3. Tez No

    75291

    Algoritma animasyonu sistemleri konusunda inceleme

    Başlık çevirisi yok

    NAZAN ÇAYRAK

    Yüksek Lisans

    Türkçe

    Türkçe

    1998

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Kontrol ve Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. TAKUHİ NADİA ERDOĞAN

  4. Tez No

    258719

    Evrensel aydınlatmada kullanılan foton haritalama yönteminin paralelleştirilmesi

    Parallelization of photon mapping technique used in global illumination

    YUSUF YAVUZ

    Yüksek Lisans

    Türkçe

    Türkçe

    2009

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAnkara Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. SÜLEYMAN TOSUN

  5. Tez No

    39800

    Üç boyutlu canlandırma sisteminde gerçeğe benzetme

    Başlık çevirisi yok

    HÜNKAR ÜNVERDİ

    Yüksek Lisans

    Türkçe

    Türkçe

    1994

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    DOÇ.DR. FÜSUN TUNALI

Geri Dön