[boost] Re: [Boost-announce] Formal Review Tribool

From: Haim Cohen (haim.cohen_at_[hidden])
Date: 2004-05-23 03:23:15

Sorry, I forgot to say explicitly that I think tribool *should be* part of boost.

Haim

Haim Cohen wrote:
> Hi,
> 
> I am happy to contribute my review for the tribool library.
> I am a software engineer developing EDA (Electronic Design Automation) 
> software, so I think I can
> contribute my 2 cents to the review of tribool, as I think EDA tools 
> will benefit from this library.
> I did not compile the library.
> I have made a quick reading of this library, but an in-depth study of 
> this problem domain before.
> 
> 
> First of all, my first comment is about the library's name, as well as 
> the class name.
> In logic circuit simulation, there are 4 values : 0, 1, x ( which is 
> tribool referred to as undetermine ), and z ( represents high impedance 
> - or
> disconnection, and sometime referred to as "tri state" ).
> So, I think users will find it quite confusing when they see the 'tri' 
> in the library's name.
> Since the library implements a logic value which has some value that is 
> unknown, I would suggest 'unknown bool' or 'x bool'.
> 
> Now to the interface.
> I think that a macro which enables renaming of the x value should not be 
> supplied. This will make people's code less standard.
> Same as we all know what 'true' and 'false' mean, we should adopt a 
> unique name for 'unknown yet quite determined logic value'.
> I think the default 'undetermine' name is not a good name.
> My suggestions : logic_x, x_value, x_logic, unknwon_bool .
> I also think the default tribool constructor should create a tribool 
> object which is 'undetermine'. (Not false, as in the documentation)
> Besides the above, I think the interface of the class is good and succinct.
> 
> Some point for thought : Users might want arrays of tribools, with all 
> the support of bitwise operations.
> Is this should be a part of tribool as well ? I do not know.
> 
> Now I will refer to the implementation.
> In real-life problems, programs might make a heavy usage of the tribool 
> class for simulations of logic circuits.
> A logic circuit (at least the combinatoric part) is a DAG where nodes 
> are logic gates, and directed archs are wires.
> This graph might be the result of a synthesis process, where a high 
> level language for hardware description (e.g Verilog) is compiled into
> this DAG. Note : This is a very general and simple description of the 
> process. Life are much more difficult.
> So, outputs will be calculated by performing lexicographic order of the 
> DAG, and calculating from inputs to outputs.
> I am telling this, to convince that performance is *very* important here.
> 
> With a quick look at the implementation code, I think that calculating 
> the value using branches (if else) will not result with good performance.
> Calculations with true/false values only is fast - CPU vendors dedicate 
> special hardware for this, so calculation can be made in one machine cycle.
> Even bitwise calculation (up to some word width) is done in one machine 
> cycle.
> Compilers are making use of this, and (hopefully) compiles boolean and 
> bitwise operators to the appropriate instruction.
> Unfortunately, I did not see any CPU which supports built in 
> true/false/X arithmetic. And even if there are such CPUs available, we 
> will not be able
> to use it, since boost libraries should be portable.
> 
> So, it is very tempting to think - how can we implement efficient 
> true/false/X arithmetic using the existing boolean arithmetic ?
> One tempting idea is to represent true/false/X with some integers, and 
> use bitwise arithmetic to get the right results.
> It seems there are no such integer values. I think I even managed to 
> proof this.
> 
> Since there is already a library implementing 4 values logic (0,1,x,z) - 
> which is SystemC - I took a quick look on how they do it with their 
> 4-states
> logic data type called sc_logic.
> They use an approach which I think should be also used in tribool.
> It seems that they maintain lookup tables for each operation: AND, OR, 
> NOT, XOR (!=) and XNOR (==).
> As the internal representation of tribool is enumerated type, we can use 
> the integer value of this enumerated type to access
> the lookup tables (primitive 2D fixed-size and fixed-values arrays) and 
> get the result of the calculation.
> This will be much faster since most CPUs has a special addressing mode 
> for accessing arrays.
> So, I suggest to change implementation to use class-static fixed array 
> to perform calculations.
> 
> I know that the spirit of Boost is portability and not performance, but 
> since what is suggested here is actually very similar to a primitive
> data type which might be heavily used in applications, I think it is 
> important to consider performance as well.
> 
> I hope this review would be found useful.
> 
> Haim
> 

-- 
_____________________________________________________
Haim Cohen
Software Engineer
haim.cohen_at_[hidden] / haimcohen2002_at_[hidden]
Analog Devices
Israel
(972) - 9 - 9715 406