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