Yazan : Şadi Evren ŞEKER

Bu yazının amacı, bilgisayarda yazılan bir kodun, derlendikten sonra bilgisayarda çalışması için geçen zamanın nasıl hesaplandığını açıklamaktır.

Bu yazıyı okumadan önce, aşağıdaki yazıların okunması faydalı olacaktır:

Çok sayıda kod yazıyor ve bu kodları bilgisayarımızda çalıştırıyoruz. Bir programın çalışma süresini bulabilmek için, hemen her dilde bulunan zaman fonksiyonları kullanılabilir. Örneğin aşağıdaki yazıda C dili ile bir programın çalışma süresinin hesaplanması anlatılmıştır:

Acaba bütün bunların yanında, programı çalıştırmadan, bilgisayarın donanım bilgilerine ve programın koduna bakarak, programın çalışma süresini kesin olarak bilebilir miyiz?

Bu sorunun cevabı ne yazık ki hayırdır. Yani bir programın, bırakın çalışma süresini, bitip bitmeyeceğini bile kesin olarak bilemeyiz. (bkz. Durma Problemi (Halting Problem))

Ancak soruyu, TAHMİN şeklinde değiştirirsek bazı şeyler söylenebilir.

Özellikle yüksek miktardaki işlem gerektiren ve uzun süre çalışacak olan kodlarda, (örneğin veri güvenliği ve şifreleme için kullanılan saldırı programları) için çalışma süresi hesaplamasında parçala fethet (divide and conquere) yaklaşımı sıklıkla kullanılmaktadır. Bu konuyu basitleştirmek için, bir örnek üzerinden açıklamaya çalışalım.

Örneğin bin kere dönecek bir döngü bulunsun. Bu döngünün, elimizdeki donanımla, toplam çalışma süresini hesaplamak için, örneğin 10 kere dönüşünü ölçüyoruz ve basitçe bu sürenin 100 misli vakit alacağını söylüyoruz ve elbette bunun tahmini bir süre olduğunu mutlaka ekliyoruz J

Şayet elimizde hiç çalışma örneği yoksa bu durumda biraz daha hesaplama yapmamız gerekiyor.

Öncelikle yüksek seviye programlama dillerini (C, C++, JAVA veya C# gibi dilleri) kullanarak bu hesaplamayı yapma şansımız ne yazık ki bulunmuyor. Mümkünse doğrudan makine diline inerek makine dilindeki komutlara (instructions) bakıyoruz. Ancak yeterli bilginiz varsa, yüksek seviye dillerden makine diline geçişi hesaplayan bir formül (örneğin kullandığımız her fonksiyonun makine dili karşılığını biliyorsak (örneğin printf fonksiyonunun karşılığını)) bu durumda tahmin işlemi yapılabilir.

Makine dilini elde ettikten sonra (ki aslında bütün derleyicilerin(compiler) işi, verilen kodu makine diline çevirmektir, dolayısıyla programımızın makine dili karşılığını bilmiyorsak basitçe derlememiz yeterlidir J), basitçe işlemcinin (CPU) her saat tikinde (clock tick) bir işlem yapacağını söyleyebiliriz.

Bu işlem, işlemcinin (CPU) tasarımına göre değişmekle birlikte, genelde 4 adımdan oluşur (Fetch, decode, execute , store işlemleri). Bu işlemlerin elbette çalışma sırasında borulama (pipelining) gibi iyileştirmelerle hızlandırılması mümkündür. Ancak işlemci tasarımcıları genelde birim zamanda ne kadar işlem (instruction) çalıştırılacağını bildirirler.

Örneğin günümüzde de kurumsal bir firma olarak faaliyetlerine devam eden MIPS (ki şu anda ismi değişmiştir) 1980’li yıllarda ilk ismini duyururken, Million Instructions Per Second (saniyede milyon işlem) olarak duyurmuştur. Bunun anlamı, bir saniyede bir milyon işlemin (insturction) yapıldığıdır.

Örneğin 1999 yılında piyasaya sürülen Intel Pentium II işlemcinin 500Mhz. İle çalışırken saniyede 1.354 MIPS işlem gücü olduğu duyurulmuştur. Bunun anlamı, yaklaşık bir buçuk milyon işlemin (instruction) saniyede yapılabildiğidir.

Dolayısıyla, şayet elimizdeki işlemcinin, işlem gücünü biliyorsak ve çalıştıracağımız kodun toplamda ne kadar işlem (instruction) çalıştıracağını biliyorsak (ki bunun için basit bir derleme yeterli olacaktır) ve işletim sisteminin, bu kaynağın ne kadarını bize ayıracağını biliyorsak süreyi hesaplayabiliriz.

Burada, birden fazla işlemi aynı anda çalıştırmak için, işlemci kaynaklarını paylaştıran işletim sistemlerinin (operating systems) kaynak ayırımı da önemli bir rol oynamaktadır.

Yorumlar

  1. serifyesil

    Sadi Bey merhaba,
    Şu anda sıralama algoritmaları ile ilgili bir ödev hazırlamaktayım. Bir algoritmanın çalışma süresini clock tick ile ölçmem isteniyor.(clock () fonksiyonu aracılığıyla c++ dilinde) Fakat aynı algoritmayı birkaç kez çalıştırdığımda clock tick sayılarım farklı oluyor. Ve time complexity leri yakın olan algoritmalar da clock ticklerin sayıları çok yakın oluyor. clock() fonksiyonu yerine algoritmaların yaptığı kıyaslama işlemlerini saysam, işlem sayılarına göre çizdiğim grafikler daha faydalı olur mu?

  2. serifyesil

    Düzeltme: quick sort ve insertion sort algoritmaları için kıyaslama işlemlerini sayıyorum. radix sort içinde dizi elemanlarını gruplarken yaptığım işlem sayısını sayıyorum.

  3. Şadi Evren ŞEKER Article Author

    C dilinde programlardan bahsettiğiniz şekilde sürenin nasıl okunacağını açıklayan bir yazı zaten bulunuyor:

    http://www.bilgisayarkavramlari.com/2009/01/01/c-ile-zaman-islemleri/

    bağlantısından erişebilirsiniz. Ayrıca sıralama algoritmaları gibi farklı sürelerde çalışan algoritmaları karşılaştırıyorsanız, mümkünse çok sayıda elemanı sıralamayı deneyin. Örneğin yüz veya bin eleman gibi sıralama işlemi sırasında farkı göremeyebilirsiniz, özelliklede çok işlemli (multi processed) işletim sistemlerinde zaman karşılaştırması böyle az sayılı sıralama işlemleri için hatalı olabilir.

serifyesil için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir