16 veya 32 bit carpma işlemi

[mr.engineer]

Merhaba bir MCU'nun datasheetinde ilk sayfada 8 bitlik iki sayıyı veya 16 bitlik iki sayıyı tek clock cycleda carpabilir gibi bilgiler var.

Detaylı bakınca instruction sette 16 bitlik sayıları toplama, bölme, 32 bitlik sayıları toplama ve bölme için instructionlar var.


Fakat hiçbir yerde 32 bitlik sayıları çarpma diye bir şey geçmiyor. Yani elimde iki tane 32 bitlik sayi var ve bunları çarpmam sonucunca 64 bitlik bir sayı almam bir hataya sebep olur mu? (uint64_t gibi bir türe kaydedecem)
İşlemci bunu tek clockda olmasa bile birkac clock cycleda yapamaz mı?

[Tagli]

Yapabilir, sorun olmaz. Hatta çarpma işlemi sırasında belki 8x8 veya 16x16 donanımsal desteğinden faydalanarak süreci bir derece hızlandırabilir. Ancak belki 64x64 çarpma işlemini derleyici desteklemeyebilir. Bu işlemciye değil derleyiciye bağlı bir durum.

[power20]

Optimizasyon olmadığı zaman çarpma işlemi için donanımsal çarpıcı  kullanılmadığını duymuştum. ( eski mplab C18)

[mr.engineer]

Hocam peki datasheette neden sadece 8 bitlik ve 16 bitlik çarpma işlemleri varmış gibi bilgi veriliyor?

[power20]

Yazılımsal olarak çarpma ile donanımsal çarpma arasında çok önemli hız farkı var. Yazılımın sınırı olmadığı için belgelerde donanımsal olanı yazmışlar. Hız için asıl önemli olan odur.

Süre sorunu yoksa  parçalara serilere ayırarak  uzun sürede iki adet 64 bit sayı çarpılabilir. Hafıza yeterliyse  "Çarpım tablosu" kullanılarak  büyük sayılar daha kolay çarpılır.

[Tagli]

Hocam peki datasheette neden sadece 8 bitlik ve 16 bitlik çarpma işlemleri varmış gibi bilgi veriliyor?

Datasheet işlemcinin donanım özelliklerini anlatır. Derleyici özellikleri datasheet'in kapsamında değildir.

[mr.engineer]

Yazılımsal olarak çarpma ile donanımsal çarpma arasında çok önemli hız farkı var. Yazılımın sınırı olmadığı için belgelerde donanımsal olanı yazmışlar. Hız için asıl önemli olan odur.

Süre sorunu yoksa  parçalara serilere ayırarak  uzun sürede iki adet 64 bit sayı çarpılabilir. Hafıza yeterliyse  "Çarpım tablosu" kullanılarak  büyük sayılar daha kolay çarpılır.

Tam anlamadım. Yazılımsal çarpma ve donanımsal çarpma farkı nedir? Hepsinde bir ALU birimi aritmetik işlemleri yapmak için var diye biliyorum.
Galiba ekstradan bir donanım daha oluyor çarpma veya bölme işlemleri için. Bunu mu kastediyorsunuz?

[power20]

MCU da çarpma donanımı yoksa, sayıları çarpmak için toplama yapılır.

Örneğin 3x254 sonucunu bulmak için 254 sayısı başlangıçta sıfır olan 16bit sayımıza 3 defa ilave edilir. 243x185 sonucunu bulmak için daha fazla toplama gerekir.
Çarpılacak sayıların her biri 16 bit olsa yine benzer yöntemlerle zahmetli şekilde sonuç bulunabilir.

Yazılımsal  çarpma ifadesi hatalı olabilir. Benim kastettiğim buydu

[yas]

MCU da çarpma donanımı yoksa, sayıları çarpmak için toplama yapılır.

Örneğin 3x254 sonucunu bulmak için 254 sayısı başlangıçta sıfır olan 16bit sayımıza 3 defa ilave edilir. 243x185 sonucunu bulmak için daha fazla toplama gerekir.

Aslında her ne kadar sonuca böyle ulaşılıyor olsa da hiçbir derleyicinin bu yöntemi kullandığını zannetmiyorum. Örnekle anlatmak gerekirse 2 adet 8 bitlik sayıyı çarpmak en fazla 8 döngüde sola kayma ve toplama işlemiyle hallolur. İkilik tabanda daha iyi anlaşılacağını düşündüğüm için yukarıdaki (243x185) çarpım örneğini ikilik sistemde işleme alarak anlatmaya çalışayım. Onluk yada onaltılık yapılmasında da bir engel yok.

243 = %11110011 çarpılan sayı
185 = %10111001 çarpan sayı
Çarpılan sayıyı çarpan sayının 1 olduğu bitlerin sırasının 1 eksiği kadar sola kaydırarak (başka değişle 2 ile çarparak) sonuçların toplanması sonucu verecektir. Yani 185 sayısında 5 adet bit 1 olduğu için 5 adet toplama işlemi yapılacak.
Sonuç 16 bitlik olacağı için anlatım rahat olsun diye üst bitleri 0 ile doldurdum.
%0000000011110011 = 243
%0000000010111001 = 185
==================
%0000000011110011 = 243 (185 sayısının sıfırıncı biti için işlem)
%0000011110011000 = 1944 (185 sayısının üçüncü biti için işlem)
%0000111100110000 = 3888 (185 sayısının dördüncü biti için işlem)
%0001111001100000 = 7776 (185 sayısının beşinci biti için işlem)
%0111100110000000 = 31104 (185 sayısının yedinci biti için işlem)
==================
%1010111110011011 = 44955
Görüldüğü üzere ikili tabanda yada onluk tabanda da sonuçlar birbirini sağlıyor.

[power20]

@yas arkadaş güzel anlatmışsınız fakat ben anlayamadım.

Örneğin 3 ve 7 yi çarpacak olalım. Bunu kaydırma ve toplama ile nasıl yapıyoruz?

 Yukarıda yazıyor fakat baktım baktım anlayamadım.  üçüncü biti için işlem? nasıl oldu inanın anlamadım

[yas]

İkili sistemde anlatmaya çalışmamın sebebi bit kaydırmayı daha rahat anlatabilmek içindi. Misal windows hesap makinesi açıp hesap makinesi türünü "programcı" olarak seçtiğimizde yapacağımız matematiksel işlemlerin hepsi bit olarak olarak işlenir. Başka bir değişle girdiler ve sonuçlar tam sayıdır. 3 ile 7 örneğini anlatayım. Sağlamasını yapmak isteyen olursa hesap makinesini programcı modunda kullanarak yaparsa daha iyi anlayacaktır.

Çarpmanın en temel iki kurallarından birisi bir sayı "0" ile çarpılırsa sonuç sıfır olur. Bir sayı "1" ile çarpılırsa sonuç kendisine eşittir.

Bir başka kuralda (ilk okul yıllarından beri öğretilen) çarpılan sayı ile çarpan sayı alt alta yazılır. Çarpan sayının birler hanesi çarpılan sayının birler hanesi ile çarpılır sonuç birler hanesine yazılır, sonuç 9 dan büyükse elde alınır, daha sonra varsa onlar hanesi çarpılır eldeki sayı çarpıma toplanır ve onlar basamağına yazılır. Bu işlem kaç hane varsa yüzler, binler, onbinler diye devam eder. Eğer çarpan sayı tek hane değilse bir alt satıra geçilir ve bir dijit soldan başlanarak aynı işlemler tekrarlanır. Daha sonra elde edilen satırlar toplanır. Eğer çarpan dijitlerden birisi "0" ise o satır tamamen sıfır olur. Eğer çarpan dijitlerden birisi "1" ise o çarpılan sayı aynen satıra yansır. Bu yansıma esnasında dijit birler basamağından farklı bir konumda ise konumuna göre sola kaydırılarak yazılmış olur.
Gelelim neden ikili(binary) sayı sisteminde anlatmaya çalıştığıma (kaçıncı defada geleceksem artık  ). İkili sistemde "0" ve "1" değerlerinden ibarettir. Hepimizin bildiği üzere bir bit 2 değer alabiliyor. Bu sebeple sıfırıncı bitin yetmediği diğer durumlar için birinci, ikinci, üçüncü....n'inci bitler devreye giriyor.
Basamakta taşma olduğu zaman elde alınan rakamın sonraki basamağa aktarılması kuralı toplama içinde geçerli bir kuraldır. Onlu sistemin taşma sınırı "9" ise ikili sistemin taşma sınırıda "1" dir.
Bu kurallar çerçevesinde ikili sistemde 0+1=1 , 1+0=1 , 1+1=10 , 1+1+1=11 vs.. olur.
Örneğe dönersek;
%00000011 = 3 (bu çarpılan sayı olsun)
%00000111 = 7 (buda çarpanımız olsun)
Aşağıda çizdiğim resimde işlemler anlaşılır umarım.




İşlemlerde görüldüğü üzere "0" ile çarpıp toplamanın bir anlamı olmadığı için sadece "1" olan bitler değerlendirmeye alınarak mcu da işlem optimizasyonu sağlanabilir.

[mr.engineer]

Hocam anlatımınız için teşekkürler.

Ama sorunu çözemedim:)
Bir IIR filtre fonksiyonu için sormuştum bunu. Fonksiyonda çok fazla shift ve çarpma işlemi var. Mcu 16 bitlik. Mesela bir yerde 4 milyon ile 1.5 milyon gibi iki sayıyı çarpıp 16 kez falan shift ediyoruz. Maalesef bu işlemden doğru sonuç çıkmıyor. Her yerde assembly kodu önerilmis şu an onları araştırıyorum. Tam sayılar yerine double kullandım ama yine fayda etmedi zaten pek önerilen bir şey de değil:)

[yas]

Sorunun sebebi double'ın derleyicide kayar noktalı olarak işlenmesinden olabilir. IEEE754 formatında işleniyorsa 63. bit sing sonraki 16 bit exponent, geri bitler mantissa olarak değerlendirilecek. Bitlerin tamamının tam sayı elemanı olarak kullanılamaması durumu uzun sayılarda taşmalara sebebiyet verecektir. Üç önerim var;
-Birincisi, asm ile 64 bitlik çarpma yapacak bir kod oluşturmak. Siz galiba şuan bunu araştırıyorsunuz.
-İkincisi, çarpılacak rakamlar örneğinizdeki gibi bol sıfırdan oluşuyorsa, mesela verdiğiniz örnekteki gibi son dijitlerde 5 tane "0" her zaman oluyorsa rakamları 10000'e bölüp işledikten sonra 10000 ile tekrar çarpın.
-Üçüncüsü, çarpılacak rakamlar örnekteki gibi bol sıfır içermiyorsa rastgele değerler alıyorsa bu değişkenleri 32 bit float olarak atayın ve yine uygun oranda bölerek fonksiyonda işleyin. Örneğin; 4.123.456 değeri ile 1.567.891 değeri çarpılacak olsun. Bu değerleri önce 1.000.000'a bölerek küçültün sonra 4,123456 x 1,567891 değerlerini çarpın sonra bunları tekrar 1.000.000 ile çarpın. Fakat bununda bir dezavantajı var. Bu dönüşümlerde ister istemez küsuratlar yuvarlanacak. Mesela Bölme işleminden sonra 4.123.456 sayısı 4,123'e 1.567.891 sayısı 1,568'e dönüşmüş olabilir. Bu yuvarlamalar sonucunda oluşacak çarpım hataları çok kritik değilse ihmal edilebilecek toleranslar içerisindeyse bu yöntem kullanılabilir.

[mr.engineer]

@yas hocam ikinci ve üçüncü yöntem işe yaramıyor. Veri kaybı çok oluyor. Tek yöntem birincisi gibi. Teşekkürler