Efficient Combinational Circuits for Constant Division

Abstract

Sabit sayılarla bölme işlemi, özel bir işlem operatörü aranmasını gerektirecek kadar sıklıkla karşılaşılan bir problemdir. Bu işlemi gerektiren sistemlerin çoğu işleyiş açısından kesirli tek bir sonuç yerine ayrı birer bölüm ve kalan içeren sonuçlar gerektirirler. Bununla beraber, sabit sayılarla bölme işlemlerinin sistem içerisinde genellikle hızlı ve tekrarlı bir şekilde çalışıyor olmaları beklenir. Bu çalışma, sabit tam sayılarla bölme ve sonuç olarak yine bir tamsayı bölüm ve tamsayı kalan elde eden sistemleri konu alır ve bunun yanında sayı tablosu tabanlı yeni bir sabit sayılarla bölme metodu sunar. Genel bölme işlemi her ne kadar zahmetli olsa da, sabit sayılarla bölme durumu bize bölen sayısını önceden biliyor olma lüksünü sağlayıp buna bağlı performans iyileştirmelerine olanak tanır. Dijital ortamda sayı tabloları, karmaşık hesaplamalardan kurtulabilmek için derleme zamanında yapılabilecek olan hesaplamaları önceden yaparak hafızada saklayabilmemizi sağlar. Sabit sayılarla bölme durumunda da bölen sayıyı biliyor olduğumuz için sonuçları sayı tablolarında saklama seçeneğimiz vardır. Fakat bütün olası girdiler için bölüm sonucunu sayı tablolarında saklamak devre kaynakları kullanımını olumsuz bir şekilde arttıracak, ve özellikle geniş bit uzunluğunda olan devreler için bu yöntemin uygulanabilirliğini imkansız kılacaktır. Bu çalışmada, geniş bit genişliklerinde de sayı tabloları yönteminin hızından faydalanabilmek için yeni bir yöntem sunuyor ve bu yöntemle en yakın rakip yönteme kıyasla 30% oranında bir hız artışı sağlabildiğini, devre kaynakları kullanımının ise hala makul seviyelerde tutulabildiğini gösteriyoruz. Son olarak değer aralıkları arasında seçim yapabilen, en uygun donanım tanımlama dili kodunu oluşturan bir RTL üreteci sunuyoruz.

Division by an integer constant is an operation that occurs so often to justify a customized implementation for it. Many systems that require such divisions mostly demand exact integer quotient and exact integer remainder results instead of a single fractional result. Besides, the constant division operations are usually required to process rapid and repeated calculations in the system, so the performance parameters for constant division gets more importance. This study examines the division circuits for constant integer dividers yielding an integer quotient with an integer remainder (i.e. Euclidean division) and proposes a fast Look-Up Table (LUT) based combinational constant division method with a binary tree like approach. Although general division is a laborious arithmetic operation, constant integer division provides us the luxury of knowing the divisor at compile time. For integer division, the division circuit is uniquely generated for division with a single integer constant. Given the divisor beforehand, LUTs can be used to store the results at compile time. But as the dividend bit-width increases, the LUT sizes increase exponentially, thus resulting an area-inefficient solution. This research introduces a binary tree approach to LUT-based integer division models. The method greatly reduces calculation time, increasing the run-time efficiency. The timing improves over 30% for input bit widths of 24 bits when compared to the latest LUT-based method and gets better as the bit width increases. The study also includes a detailed comparison between LUT based methods and other known integer division methods.