Modular Types

Proposal Details

• Who Updates:
• Date Proposed:24 July 2014
• Date Last Updated:24 July 2014
• Priority:?
• Complexity:?

Current Situation

There is no modular type in the language. Ada has one

There is not support of boolean and shift operations on integers (see http://www.eda.org/twiki/bin/view.cgi/P1076/IntegerOperators ) and this forces the use of implementation-dependent code for efficient behavioural simulations (which might push developers to use other languages like SystemC). However, adding bool/shift to the integer type creates problems that are solved naturally by a modular type -- YannGuidon - 2014-07-24

Requirement

The minimum requirements are:

• Modular types must not restrict the values allowable for modulus.
• Modular types which are modulo-power-of-2 must allow logical and shift operations (using native instructions)
• Modular types which are modulo-power-of-2 should map to bit_vector, signed, unsigned or std_(u)logic_vector during synthesis

Implementation details

Two possible implementations have been discussed:

New subtype

Like is done in Ada - we could potentially follow the Ada method completely. However a couple of points were raised in relation to this:

1) Ada allows logical operations on non-power-of-2 modulus types. This is seen by some as unnecessary complication, as it would not be used. Other see it as a “tidier” language which doesn’t have different behaviours depending on the range of a type.

The result of the operator not for a modular type is defined as the difference between the high bound of the base range of the type and the value of the operand. For a binary modulus, this corresponds to a bit-wise complement of the binary representation of the value of the operand.

2) Ada currently does type-conversion slightly differently to “expected” – raising an error for input values outside of the destination modular range, rather than taking the mod as one would expect. Some discussion from the Ada community is here: http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ais/ai-00340.txt?rev=1.8

The modular type would be a subtype based on the universal integer, and would therefore gain the extended range of proposal http://www.eda.org/twiki/bin/view.cgi/P1076/ArbitraryIntegers if implemented.

Ada examples:

type Byte is mod 256; -- an unsigned byte

type Hash_Index is mod 97; -- modulus is prime

type T is mod <>; -- generic formal parameter

New Record Type

Modular types can be created using a new type based on a record that holds both the value and modulus and appropriate overloading:

package ModuloPkg is
  type ModuloType is record
    modulus  : integer ; 
    I        : integer ;
  end record ; 
  
  function SetModulous (M : Modulous) return ModuloType ;
  
  function "+" (L, R : ModuloType ) return ModuloType ; 
  function "-" (L, R : ModuloType ) return ModuloType ; 
  function "*" (L, R : ModuloType ) return ModuloType ;
  
  -- Mixed with integers, Modulo takes precedence
  function "+" (L : ModuloType ; R : Integer ) return ModuloType ; 
  function "+" (L : Integer  ; R : ModuloType ) return ModuloType ; 
  
  function "-" (L : ModuloType ; R : Integer ) return ModuloType ; 
  function "-" (L : Integer  ; R : ModuloType ) return ModuloType ; 

  function "*" (L : ModuloType ; R : Integer ) return ModuloType ; 
  function "*" (L : Integer  ; R : ModuloType ) return ModuloType ; 
end ModuloPkg ;  

With such a package, I can do the following:

library IEEE ; 
use IEEE.std_logic_1164.all ; 
use work.ModuloPkg.all ;

entity TbModuloPkg is 
end TbModuloPkg ;
architecture Test1 of TbModuloPkg is 
  signal IncReg : ModuloType := (8, 0) ;
  signal A, Y_Plus, Y_Minus, Y_Times : ModuloType := SetModulous(8) ;
  signal Clk : std_logic := '0' ;
begin

  Clk <= not Clk after 5 ns ; 
  
  IncRegProc : process (Clk) is
  begin
    if rising_edge(Clk) then 
      IncReg := IncReg + 1 ; 
    end if ; 
  end process IncRegProc ; 
  
  A <= (8, 5) ; 
  
  Y_Plus   <= IncReg + A ; 
  Y_Minus  <= IncReg - A ; 
  Y_Times  <= IncReg * A ; 
end Test1 ; 

Limitations It is intended that the modulus is static - set once at initialization, and then never changed. There is no way a synthesis tool will be able to extract this information.

While we can check that two values of type ModuloType have the same modulus, it is not possible to see that the target of the assignment also has the same modulus. The language already have this issue with respect to ranged integers. The following example demonstrates not only is it possible, it is also appropriate.

signal A, B : integer range 0 to 7 ; 
signal Y : integer range 0 to 15 ; 
...
Y <= A + B ; 

Other limitations: As this package is based on Integer, the modulus is limited to 2**31. The implementation of this package is not trivial for usual operator (how "*" is implemented ?) and not very efficient for logical operators. Furthermore, it doesn't provide strong typing as there is only one modular type and the user can change the modulus.

Generics

Tristan's comment from record approach:

A slightly better proposal could be a generic package with modulus as generic constant. -- TristanGingold - 2014-10-20

-- JimLewis -- Not sure your intent here in using generics. Are you thinking of implementing the modulus as a generic? I am not so hip to that. If you have them on a package, and you have multiple counters that use this, then each may have a different number of bits - and hence - different modulus. Each would require a separate packge instance and would have to reference its type by fully selected path. ie:

use work.ModuloPkg_modulus8.all ;
use work.ModuloPkg_modulus16.all ; 

signal Counter1Reg : work.ModuloPkg_modulus8.modtype ;  -- mod 8
signal Counter2Reg : work.ModuloPkg_modulus16.modtype ; -- mod 16

OTHO, if you put generics on a type, I am not sure how they would be visible to any function of that type. OTOH, if you used a generic to specify the base type of the ModuloType and used a discriminant, then you would have a flexible construct. -- JimLewis - 2014-10-23

package My_Modular_Types is  package mod8_pkg is new ModuloPkg generic map (modulo => 8);
  package mod16_pkg is new ModuloPkg generic map (modulo => 16);
  alias unsigned_3 is mod8_pkg.modtype;
  alias unsigned_4 is mod16_pkg.modtype;
end My_Modular_Types;
use work.My_Modular_Types.all;
...
  variable v : unsigned_3;

Discriminants

Discriminants and Modulo Types

ADA has a capability to add a discriminant to a type, such as a record type. See http://en.wikibooks.org/wiki/Ada_Programming/Types/record

ADA only allows a discriminant to be associated with a record type. This proposal adds the capability to a scalar type. Hence, this would allow modulo type to be defined as follows:

type modulo (modulus : integer) is integer ;

A discriminant is set in a signal, variable, or constant declaration and is not updated in assignments (signal or variable).

signal IncVal : modulo (modulus => 16); 

Overloaded subprograms would have direct access to the discriminant in the same way they have access to a record field.

  function "+" (L, R : modulo ) return modulo is
    variable Result : modulo ; 
  begin
    assert L.modulo = R.modulo report "Modulo required to be the same" severity ERROR ; 
    Result.I := (L + R) mod L.modulus ; 
    return Result ; 
  end function "+" ;

It would be possible to require a check that an expression and its target (assignment or mapping) have the same discriminant, or leave it flexible like integer ranges.

The type declaration would be supported by a package with appropriate overloading (if it becomes something we agree on, it could be in std.standard):

package ModuloPkg is
   type modulo (modulus : integer) is integer ;
  function "+" (L, R : modulo ) return modulo ; 
  function "-" (L, R : modulo ) return modulo ; 
  function "*" (L, R : modulo ) return modulo ;
  
  -- Mixed with integers, Modulo takes precedence
  function "+" (L : modulo ; R : Integer ) return modulo ; 
  function "+" (L : Integer  ; R : modulo ) return modulo ; 
  
  function "-" (L : modulo ; R : Integer ) return modulo ; 
  function "-" (L : Integer  ; R : modulo ) return modulo ; 

  function "*" (L : modulo ; R : Integer ) return modulo ; 
  function "*" (L : Integer  ; R : modulo ) return modulo ; 
end ModuloPkg ;  

To convert back to integer, see Implicit Numeric Conversions.

Discriminants and Saturating Types

Discriminants are a general capability. Creating other implementations, such as saturating math would simply require creating the type and overloading the functions.

Discriminants vs. Generics

In some ways discrimants are similar to generics. We may want to consider making discriminants be a generic that can be specified at usage of the object (as is done with the discriminants).

With protected types, I have a need for the capability of generics (constant, type, and subprogram) to be put on the type, but specified in the usage of the object. See proposal Generics on Types

Other potential uses of Discriminants

Array types could also benefit from having discriminants on subtype declarations. For example, we could define array types such as the following:

subtype slv (Size : natural) is std_logic_vector(Size-1 downto 0) ;

In this case, we would want to be using a subtype as we would not want to have to declare subprograms for subtype slv.

signal A : slv(8) ;

Comments

This proposal is based on Integer which isn't the best type to provide modular operations -- TristanGingold - 2014-10-20

-- JimLewis - The example uses existing VHDL types. Certainly if we extended the language to have BigNum integers, we could either use that instead. Returning to Tristan's thought about using generics, we passed the base type of the modulo type as a generic (see abstract packages proposal about importing numeric types) and made the discriminant as the same type as the base type of the ModuloType, then we would have a very flexible package. The intent of the proposal is to create a language mechanism that would allow us to create modulo or other derived types (such as saturating types) that can be applied to any type. -- JimLewis - 2014-10-23

A slightly better proposal could be a generic package with modulus as generic constant. -- TristanGingold - 2014-10-20

-- JimLewis -- If we return to Tristan's thought about generics and made the base type for the ModType be a generic passed into the package and used determinants, then we would a very powerful solution that could even use any numeric type as real numbers as the base type (if there was an application for this).

Extend use of resolution functions

A resolved subtype declaration can specify a resolution function of any name.

We would have to implement integer/natural versions of the logical operations. These would return integer/natural results. They would be much less useful without the use of modular resolved types.

The modular resolved subtype’s resolution function would then perform the modulo operation upon assignment or association to/with a signal object of the modular resolved subtype. To permit modular operations using variables, we would need to extend resolution function calls to assignments/associations to/with variables of resolved types.

Currently, the user would have to declare a unique resolution function for each value of modulus they wanted to use.

Example:

function modular8(driven_values: integer_vector) return integer is
   begin
      assert driven_values’length = 1; -- do not allow multiple drivers
      return driven_values(driven_values’left) mod 8;
end function modular8;

The above function would then be used to declare the modular subtype:

Subtype modulo8 is modular8 integer;

An alternative to modifying the syntax in the resolved subtype declaration, available today, would be to put the resolved subtype declaration in a generic package, and instantiate the package for each value of modulus (the generic) needed.

For ease of declaring modular subtypes of different moduli, we could extend the resolution function specification to include explicit arguments (not including the implicit argument that is associated with the array of driven values.)

Example:

Subtype modulo4 is modular(4) integer;

Where  modular()

is a resolution function that takes the modulus ( positive

) and an array of driven values ( integer_vector

), and returns an integer

within the range of 0 to modulus–1.

This implementation would be a major change to the operation of signal and variable assigments, so would merit very careful consideration of any potential impact on existing code.

Also, allows for other uses of resolutions (eg fixed-point result expansion) by inspecting destination type, which is potentially interesting.

Extension of RANGE system

Another low/medium complexity approach consists in extending the RANGE system, which would provide modular and saturated behaviours

subtype a : integer range 123 to 456; -- well known
subtype b : integer modular 789 to 101112; -- new
subtype c : integer saturated 131415 to 161618; -- new

This reuses the mechanisms already in place in simulators/synthesisers. Unlike packages or enhanced resolution functions, there is close to no footprint or runtime overhead. This also allows a better integration with the parser/compiler/simulator's internals, bringing better efficiency.

Through a few attributes ('HIGH, 'LOW and a couple new ones, TBD), operator overload enables correct handling of certain corner cases.

Proposal under construction.

Use Cases

• Wrap around counters (not necessarily powers-of-2). For example ATM frames are 48 bytes, so counters from 0 to 47 are common.
• Logical (AND, OR, NOT, etc.) and other bitwise (eg shifts and rotates) operations on “integer-like” items like counters, etc. No need forseen to do this on non-powers-of-2-modul
• The majority of SoC contain CPUs, crypto, ECC, graphics and other logic that are painfully slow to simulate with vanilla std_logic_vector/signed/unsigned. For example, a simple SHA-1 kernel ( http://ygdes.com/GHDL/int_bool/sha-1.vhdl ) simulates 400x faster using native integers than with std_logic_vector. -- YannGuidon - 2014-07-24

Arguments FOR

* Ease of programming, less bugs because wraparound is handled by the software,

* Speed of simulation (integers are faster than vectors-of-bits). There is less incentive to use C or other ad-hoc languages for computation-intensive tasks.

* Power-of-two moduli are directly mappable as bit vectors, signed or unsigned, so the same code works fast for simulation and for the synthesis. This reduces bugs and coding efforts.

-- YannGuidon - 2014-07-24

Arguments AGAINST

The only argument against that I can see is that "we've got on OK thus far" and that there's maybe better things to the tool implementers could spend their time on.

The resolution function is for a completely different purpose, and does not apply to intermediate expression values.

There are two alternatives which involve much less of an implementation burden:

(a) Adding logical and shift operators to integers, as in C. This will be needed in any case.

(b) Adding arithmetic operators to bit vectors, as in numeric_bit package. If moved to standard package, it may encourage better implementation.

(a) is easy to implement. It may cause compatibility problems if users have defined their own versions of these operators. The user has to remember to mask the results of the operations. This can be done by defining functions like modulo_add in a package.

(b) is cleaner and solves other problems like arbitrary size arithmetic. However its efficient implementation is more work for the tool vendor than (a). A library package will not deliver the performance desired.

-- PeterFlake - 2014-08-21

Implementing modular types shouldn't be very difficult; but bit_vector/std_logic_vector already provide this feature. If they are too slow, ask implementor to optimize them.

Modular types were mainly added to Ada for interfacing with languages like C and its unsigned types. This isn't a need for VHDL.

-- TristanGingold - 2014-10-20

Additional Arguments AGAINST

I believe the proposal for modular types goes too far. In essence, this is an attempt to replace the functionality of bit-vectors. Were bit/std_logic vectors a bad idea, and are we advocating their deprecation?

Once logical operators are defined for integers, nothing prevents a group of interested parties from defining a widely-disseminated package in which the ideas for modular types are implemented. This approach will give the community the benefit of experimenting with the modular type concept, especially when ideas like representation of ranges are still not settled. If the modular type package becomes a de facto standard, implementors will most probably develop accelerated versions of the package.

-- CliffordWalinsky - 2014-09-03

The LRM on Expressions, Type conversion tells us that integer and real types are closely related (as are array types with the same base element type) and are abstract numerical types without bit elements. Why aren't you proposing this for reals, too?

There is no basis in the standard nor any historical antecedents (e.g. CONLAN) for tying abstract numeric types to an underlying implementation element. Today VHDL (or Ada) can be implemented on non-binary arithmetic based computers and apparently there are some decimal arithmetic mainframes still hanging around the Pentagon basement, plus who knows what the future holds?. The Ada Modular types address this implementation/abstract dichotomy by describing binary operations in terms of numerical value equivalents (which most use of C does as well).

Attempting to make integer types related to an implmentation dependent machine type is a drastic change.

Further "implementation-dependent code for efficient behavioural simulations" isn't a purpose of a standards effort. See WHAT ARE STANDARDS? Performance is an implementation matter, and enforcing alignment to underlying machine types is likely not to be as productive as you might wish. The amount of time actually doing logical or arithemetic operations is likely only a small part of simulation time. There's the overhead for a simulation cycle and runtime checking for instance. The lack of 'precision' addressing performance leaves room for distinctiveness of implementations for market purposes while still allowing competitive products being compared.

The minimum requirements bit about '(using native instructions)` has nothing to do do with the language defiinition. Likewise there is no guarantee that a synthesis tool translates integer types into either bit_vector or std_ulogic_vector types and might map to an entirely different representation (e.g. bit strings for verficiation). Don't attempt to put restrictions on synthesis tools which are only constrainted by a subset of the language (should 1076.6 be replaced).

Ada doesn't use a subtype constraint to determine modularity. It uses a type attribute containing a modulus associated with a range constraint between 0 and the modulus - 1. The expectation appears to be that if a modulus attribute isn't set or defaults, that modulus reduction code not accessible by something statically declared may be optimized away. Other than added logical operators conflating abstract numerical value and logical 'bits' there is nothing new that needs to be done other than modifying integer operators for locallly static dependent modulus reduction. The Ada method of modular integers doesn't 'threaten' the definition of an integer or real as an abstract numeric type.

If I were a tool implementor (and I might be), I would see the Ada definition as the easiest to implement. It doesn't by itself imply any massively greater performance imperative either.

This present effort seems better suited to a new language definition instead of remaking VHDL into a SystemVHDL. One way to understand this is to invision the impact on the standard. Changes involving high page counts are indicative that other special interests in a Sponsor gathered voting group are likely to either abstain or vote against lacking involvement during the standard change development phase and not easily able to test the premise so presented during the voting period. Without a working implementation this proposal seem premature.

-- DavidKoontz - 2014-10-26

General Comments

Decisions still to be made:

* Should logical etc operators be allowed on non-power-of-2-modulus ? Or are we better expending our energy elsewhere?

* Should assignment operate like Ada or in what has been described as "the expected way"?

* Should modular types have to go from 0 to something? Or would -1 to 6 be acceptable? (just like "range" of integers ?) And would it allow logicals, shifts and rotates?

Supporters

-- Main.MartinThompson - 2014-07-24

-- YannGuidon - 2014-07-24

Add your signature here to indicate your support for the proposal

Non-supporters

-- DavidKoontz - 2014-10-26

Add your signature here to indicate your support for the proposal