bluespec.com Forum Index bluespec.com
Bluespec Forums
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Opaque types in interfaces

 
Post new topic   Reply to topic    bluespec.com Forum Index -> Designing with BSV's Rules, Interfaces, ...
View previous topic :: View next topic  
Author Message
mcadler



Joined: 20 Aug 2007
Posts: 18

PostPosted: Tue Apr 17, 2012 9:47 am    Post subject: Opaque types in interfaces Reply with quote

I can't figure out how to accomplish the following:

I want an interface to a filter for some type that has two methods: test and set. The implementation is a wrapper module that may pick a different low-level implementation based on the size of the type. The test method computes whether set is permitted but may also compute some state that it would be efficient not to have to recompute in set. So, I want test to return a Maybe#(t_OPAQUE), where the client just cares whether the maybe is valid. This:

Code:
interface FILTER#(type t_ENTRY);
    method Maybe#(t_OPAQUE) test(t_ENTRY newEntry);
    method Action set(t_OPAQUE stateUpdate);
endinterface


And a wrapper module such as:

Code:

module mkFilter
    // interface:
    (FILTER#(t_ENTRY))
    provisos (Bits#(t_ENTRY, t_ENTRY_SZ));

    let filter = ?;

    if ((valueOf(t_ENTRY_SZ) > 10))
    begin
        // Large sets use Bloom filters
        BLOOM_FILTER#(t_ENTRY, 128, 2) bloomFilter <- mkBloomFilter();
        filter = bloomFilter.filterIfc;
    end
    else
    begin
        // Small sets get unique bit per entry
        DECODE_FILTER#(t_ENTRY, TExp#(t_ENTRY_SZ)) decodeFilterS <- mkSizedDecodeFilter(debugLog);
        filter = decodeFilterS.filterIfc;
    end

    return filter;
endmodule


The Bloom filter wants to return the results of the hashes from test and have them passed to set instead of recomputing the expensive hashes again in set. The decode filter could return the index, too, though computation there is trivial.

Any suggestions? I'm trying to keep the interface to FILTER simple while still generating good code.
Back to top
View user's profile Send private message
jnewbern



Joined: 18 Jul 2007
Posts: 71

PostPosted: Tue Apr 17, 2012 12:52 pm    Post subject: Reply with quote

Michael,

Here are a few suggestions, in order of desirability:

1. If the semantics of the filter interface allow it, you can return only a Bool saying whether the result is valid and keep the actual state update data inside of the filter module. This is the cleanest solution for the interface to the caller because it becomes:

Code:
interface FILTER#(type t_ENTRY);
   method Bool test(t_ENTRY new_ENTRY);
   method Action set(); // or update, or some other name
endinterface


2. You can define a tagged union for the t_OPAQUE type and have each filter type use one of the variants. This will not keep the t_OPAQUE type out of the interface entirely (as option #1 does), but it does keep it from being a required type variable for the FILTER interface. This will rely on downstream tools to do a good job optimizing away the unused portions of the tagged union for each individual filter instantiation.

3. You can use type classes with functional dependencies to perform the necessary type selection, with an interface that exposes the t_OPAQUE type variable:

Code:
interface FILTER#(type t_ENTRY, type t_OPAQUE);
   method Maybe#(t_OPAQUE) test(t_ENTRY newEntry);
   method Action set(t_OPAQUE stateUpdate);
endinterface


But this will be complicated to code and expose the user to more type-level manipulations than you (or they) would probably like.
Back to top
View user's profile Send private message
quark
Site Admin


Joined: 02 Nov 2007
Posts: 499

PostPosted: Tue Apr 17, 2012 1:16 pm    Post subject: Re: Opaque types in interfaces Reply with quote

I'm not sure I follow, but I'll try to answer. First, what's wrong with what you've written? I'm not sure I understand what barrier you're hitting. Second, I'm not sure I know enough of the context to know what I'm allowed to change. For instance, can you use this interface:
Code:
interface FILTER#(type t_ENTRY);
   method Bool test(t_ENTRY newEntry);
   method Action set();
endinterface

and have the filter just contain a register in which it stores the hash? So that a call to "set" will use the result of the previous call to "test". Or is the use of the interface asynchronous, so that multiple calls to "test" might occur before the call to "set" with an older result?

And what do you mean by "expensive"? Can you share the same hash logic between the "test" and "set" methods or do you need to support simultaneous calls?

At worst, I think you might have to do this:
Code:
interface FILTER#(type t_ENTRY, type t_HASH);
   method Maybe#(t_HASH) test(t_ENTRY newEntry);
   method Action set(t_HASH);
endinterface

And you could set the "t_HASH" type to "void" for filters that don't need it (and the 0-bit value should get optimized away?). Exposing the type in this way should only be required in situations where the caller needs to know the type anyway (for instance, if you plan to make asynchronous calls to "test" and "set", so you need to tag entries with their hash, so you're planning to store the hash value anyway).

Does any of that help or am I off track?
Back to top
View user's profile Send private message
mcadler



Joined: 20 Aug 2007
Posts: 18

PostPosted: Tue Apr 17, 2012 1:45 pm    Post subject: Reply with quote

Quark's is essentially Jeff's 1st and 3rd options, so I'll lump the two responses together.

The 3 options are what we considered, too. Ideally, we wished t_OPAQUE were bound by the compiler to whatever makes sense during static elaboration, but the compiler appears unwilling to do that through an interface.

Option 1 (Bool test and store intermediate state inside the implementation) is difficult if I want to be able to call test/set either in the same rule or in separate rules on separate cycles. It also doesn't work if I might call test in parallel from two different rules and pick a winner that may call set from among the tests that pass.

Option 3 replicates too much of the existing static elaboration logic as type logic. It could work but is aesthetically unappealing and harder to maintain.

We had considered option 2 (tagged union) and think it is probably the best choice for us in this case.

If I write the code given in my first example, the compiler emits:

Quote:
Signature mismatch (given too general):
given:
function Maybe#(a__) f(t_ENTRY x1)
deduced:
function Maybe#(Bit#(TLog#(nFilterBits))) f(t_ENTRY x1)


Why can't the compiler promote a__ to Bit#(TLog#(nFilterBits)) at this point and let the logic run its course? Why not fail at the point that specific types mismatch as opposed to one general and one specific? At first I had hoped that the error message meant I just had to assert that the return type for test was bits by saying Maybe#(Bit#(t_OPAQUE)) in the interface, but that still triggers a variant of the above error.
Back to top
View user's profile Send private message
quark
Site Admin


Joined: 02 Nov 2007
Posts: 499

PostPosted: Tue Apr 17, 2012 2:53 pm    Post subject: Reply with quote

(A) I'm not sure I follow why option 3 is unappealing or harder to maintain. I think I'd need to attempt a concrete example, to see.

Also, I don't see what you're worried about option 3 duplicating. I'd be more concerned that option 2 is duplicating type checking in the actual hardware: option 2 (tagged union) instantiates extra signals for the tags and logic to check the tags, even though the tag is never going to change (because you picked it at compiled time). It's basically implementing option 3 at run time; option 3 does it at compile time, so no extra logic is generated in the hardware.

Again, maybe a concrete example is needed.

(B) The "too general error" definitely needs improvement, and I apologize that it's not clear. The code as you originally wrote it does have one problem that you need to change. You should not write this:
Code:
interface FILTER#(type t_ENTRY);
    method Maybe#(t_OPAQUE) test(t_ENTRY newEntry);
    method Action set(t_OPAQUE stateUpdate);
endinterface

You should not use a type variable inside an "interface..endinterface" block that does not appear in the parameter list. So you should add "t_OPAQUE" to the parameter list (or remove it).

What you have written could possibly be useful, but 99.9999% of the time, it's not what you want. It's an unfortunate feature of BSC that you can so easily write the above definition -- the BSV syntax should probably require an explicit syntax for this case, to force the user to say that he really is sure that this is what he wants, and that he hasn't just accidentally written it.

What you've written has declared that "set" is polymorphic: it can return any type at all, any time you call it! It's saying that, even after you instantiate a specific module that provides this interface, you're free to call "set" multiple times and give it different argument types each time -- here you call it with Bool, there you call it with Bit#(8) -- the instantiation is not specifying a specific type. ... If what you intended was for the instantiation to fix the type "t_OPAQUE" to a specific type, then it should be included in the parameter list for the interface.

The "too general" error should be more clear about this, sorry. Instead of mentioning variable "a__", it should be pointing perhaps to the "t_OPAQUE" in your interface. You've declare "set" to be polymorphic, but you're instantiating a module whose interface is not polymorphic. I would expect, though, that you should get this error when BSC type checks "mkBloomFilter" -- BSC shouldn't get all the way to type checking "mkFilter" before reporting a problem.
Back to top
View user's profile Send private message
mcadler



Joined: 20 Aug 2007
Posts: 18

PostPosted: Tue Apr 17, 2012 3:06 pm    Post subject: Reply with quote

I'm trying to break apart the current interface's insert() method into two parts so that the test() and set() are separate pieces. I could then use test() as a predicate to a rule.

The current interface allows that too, with the notSet() method, at the cost of doing the equivalent of test() twice and crossing fingers that the optimizer will remove the potentially large redundant code from notSet() and insert().

Here is the current code:

Code:
//
// Copyright (C) 2009 Intel Corporation
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
//

// Library imports.

import Vector::*;
import RWire::*;

//
// Counting filters can be used to determine whether an entry is present in
// a set.  All counting filters have both insert() and remove() methods.
// This module provides multiple implementations for sets of varying sizes.
// Smaller sets can use direct decode filters.  Larger sets can use Bloom
// filters, which have more logic to deal with hashes but have good false
// positive rates with relatively small filter vector sizes.
//
// For automatic selection of a reasonable filter, use the mkCountingFilter
// module.  It picks decode filters for smaller sets and Bloom filters for
// larger sets.
//


// ========================================================================

// COUNTING_FILTER
//
//   All counting filters provide this basic interface.
//
// ========================================================================

interface COUNTING_FILTER#(type t_ENTRY);
    // Clear filter
    method Action reset();

    // Attempt to insert a new entry.  Returns true on success.  If the filter
    // already has the entry or a counter would overflow returns false.
    method ActionValue#(Bool) insert(t_ENTRY newEntry);

    method Action remove(t_ENTRY oldEntry);

    // Test whether entry is busy
    method Bool notSet(t_ENTRY entry);
endinterface


//
// mkCountingFilter --
//   Pick a reasonable filter based on the entry set size.  Uses a Bloom filter
//   for large sets and a simple decode filter for smaller sets.
//
//   If allowComplexFilters is true then larger filters, such as Bloom filters,
//   may be allocated.  If allowComplexFilters is false then only decode filters
//   will be allocated.
//
module mkCountingFilter#(Bool allowComplexFilters, DEBUG_FILE debugLog)
    // interface:
    (COUNTING_FILTER#(t_ENTRY))
    provisos (Bits#(t_ENTRY, t_ENTRY_SZ));

    let filter = ?;

    if ((valueOf(t_ENTRY_SZ) > 10) && allowComplexFilters)
    begin
        // Large sets use Bloom filters
        COUNTING_BLOOM_FILTER#(t_ENTRY, 128, 2) bloomFilter <- mkCountingBloomFilter(debugLog);
        filter = bloomFilter.countingFilterIfc;
    end
    else if (valueOf(t_ENTRY_SZ) > 7)
    begin
        // Medium sized sets share 2 bits per entry
        DECODE_FILTER#(t_ENTRY, TDiv#(TExp#(t_ENTRY_SZ), 2)) decodeFilterL <- mkSizedDecodeFilter(debugLog);
        filter = decodeFilterL.countingFilterIfc;
    end
    else
    begin
        // Small sets get unique bit per entry
        DECODE_FILTER#(t_ENTRY, TExp#(t_ENTRY_SZ)) decodeFilterS <- mkSizedDecodeFilter(debugLog);
        filter = decodeFilterS.countingFilterIfc;
    end

    return filter;
endmodule


// ========================================================================
//
// Decode Filter
//
// ========================================================================

//
// nFilterBits should be a power of 2!  Decode filter exposes
// a counting filter interface for compatibility with the Bloom
// filter.
//
interface DECODE_FILTER#(type t_ENTRY, numeric type nFilterBits);
    interface COUNTING_FILTER#(t_ENTRY) countingFilterIfc;
endinterface

//
// Decode filter with one bit corresponding to one or more entries.
// Insert and remove methods may both be called in the same cycle.
//
module mkSizedDecodeFilter#(DEBUG_FILE debugLog)
    // interface:
    (DECODE_FILTER#(t_ENTRY, nFilterBits))
    provisos (Bits#(t_ENTRY, t_ENTRY_SZ),
       
              Alias#(Bit#(TLog#(nFilterBits)), t_FILTER_IDX));

    Reg#(Bit#(nFilterBits)) fv <- mkReg(0);

    RWire#(t_FILTER_IDX) insertId <- mkRWire();
    RWire#(t_FILTER_IDX) removeId <- mkRWire();

    Reg#(Maybe#(t_ENTRY)) lastFailMsg <- mkReg(tagged Invalid);

    function t_FILTER_IDX filterIdx(t_ENTRY e);
        return truncateNP(pack(e));
    endfunction

    (* fire_when_enabled *)
    rule updateFilter (True);
        let fv_new = fv;
       
        if (insertId.wget() matches tagged Valid .id)
            fv_new[id] = 1;

        if (removeId.wget() matches tagged Valid .id)
            fv_new[id] = 0;
       
        fv <= fv_new;
    endrule

    interface COUNTING_FILTER countingFilterIfc;
        method Action reset();
            fv <= 0;
        endmethod

        method ActionValue#(Bool) insert(t_ENTRY newEntry);
            let id = filterIdx(newEntry);

            if (fv[id] == 0)
            begin
                insertId.wset(id);
                lastFailMsg <= tagged Invalid;
                debugLog.record($format("    Decode filter INSERT %0d OK, idx=%0d", newEntry, id));
                return True;
            end
            else
            begin
                // Only print insert FAIL message once
                if (! isValid(lastFailMsg) || (pack(newEntry) != pack(validValue(lastFailMsg))))
                begin
                    lastFailMsg <= tagged Valid newEntry;
                    debugLog.record($format("    Decode filter INSERT %0d FAIL, idx=%0d", newEntry, id));
                end

                return False;
            end
        endmethod

        method Action remove(t_ENTRY oldEntry);
            let id = filterIdx(oldEntry);
            removeId.wset(id);
            debugLog.record($format("    Decode filter REMOVE %0d, idx=%0d", oldEntry, id));
        endmethod

        method Bool notSet(t_ENTRY entry);
            let id = filterIdx(entry);
            return (fv[id] == 0);
        endmethod
    endinterface
endmodule



// ========================================================================
//
// Counting Bloom Filter
//
// ========================================================================


interface COUNTING_BLOOM_FILTER#(type t_ENTRY,
                                 numeric type nFilterBits,
                                 numeric type nCounterBits);
    interface COUNTING_FILTER#(t_ENTRY) countingFilterIfc;
endinterface


typedef Vector#(nHashes, Bit#(nHashIndexBits))
    BLOOM_FILTER_HASH_VEC#(numeric type nHashes, numeric type nHashIndexBits);

//
// Optimal number of hashes is probably 5 or 6, but that takes too much FPGA
// space.
//
typedef 4 BLOOM_COUNTING_HASHES;

//
// Counting Bloom filter up to 256 bits.
//
module mkCountingBloomFilter#(DEBUG_FILE debugLog)
    // interface:
    (COUNTING_BLOOM_FILTER#(t_ENTRY, nFilterBits, nCounterBits))
    provisos (Bits#(t_ENTRY, t_ENTRY_SZ),

              // nFilterBits must be <= 256 and a power of 2.
              Add#(TLog#(nFilterBits), a__, 8),
              Add#(nFilterBits, 0, TExp#(TLog#(nFilterBits))),

              Alias#(BLOOM_FILTER_HASH_VEC#(BLOOM_COUNTING_HASHES, TLog#(nFilterBits)), t_HASH_VEC));
   
    // Filter bits (counters)
    Reg#(Vector#(nFilterBits, Bit#(nCounterBits))) bf <- mkReg(replicate(0));

    // Insert and remove requests are passed on wires to a single rule so
    // both methods may be called in the same cycle.
    RWire#(t_HASH_VEC) insertVec <- mkRWire();
    RWire#(t_ENTRY) removeId <- mkRWire();
    RWire#(Tuple2#(Bit#(nFilterBits), Bit#(nFilterBits))) updateBits <- mkRWire();

    Reg#(Maybe#(t_ENTRY)) lastFailMsg <- mkReg(tagged Invalid);

    //
    // computeHashes --
    //     Calculate the set of hashes for an entry id.
    //
    function t_HASH_VEC computeHashes(t_ENTRY entryId);
        //
        // Map however many entry bits there are to 32 bits.  This hash function
        // is a compromise for FPGA area.  It works well for current functional
        // memory set sizes.  We may need to revisit it later.
        //
        Bit#(32) idx32;
        Bit#(t_ENTRY_SZ) idx_orig = pack(entryId);
        Integer b = 0;
        for (Integer i = 0; i < 32; i = i + 1)
        begin
            idx32[i] = idx_orig[b];

            b = b + 1;
            if (b == valueOf(t_ENTRY_SZ))
                b = 0;
        end

        // Get four 8 bit hashes
        t_HASH_VEC hash = newVector();

        hash[0] = truncate(hash8(idx32[7:0]));
        hash[1] = truncate(hash8a(idx32[15:8]));
        hash[2] = truncate(hash8b(idx32[23:16]));
        hash[3] = truncate(hash8c(idx32[31:24]));
   
        return hash;
    endfunction


    //
    // updateFilter --
    //
    //     Two part, single cycle rule to update the Bloom filter.  The
    //     first rule consumes this cycle's insert and remove calls and constructs
    //     a pair of vectors of filter positions that will change.  The second
    //     rule consumes those vectors as wires and updates the Bloom filter.
    //
    //     While these rules are logically a single rule, combining them causes
    //     the Bluespec optimizer to attempt to figure out exactly which bits
    //     changed and the combinatorics grow quite large.
    //

    (* fire_when_enabled *)
    rule updateFilter1 (True);
        //
        // Construct a vector of filter positions to increment.
        //
        Bit#(nFilterBits) bf_up = 0;

        if (insertVec.wget() matches tagged Valid .hash)
        begin
            for (Integer i = 0; i < valueOf(BLOOM_COUNTING_HASHES); i = i + 1)
            begin
                bf_up[hash[i]] = 1;
            end
        end

        //
        // Construct a vector of filter positions to decrement.
        //
        Bit#(nFilterBits) bf_down = 0;

        //
        // Removal request comes in as the index to the filter instead of a
        // set of hash buckets.  This puts the computation of hashes in a single
        // rule.  We would do this for the insert request, too, except that
        // the insert method returns a response that is a function of the hashes.
        //
        if (removeId.wget() matches tagged Valid .remId)
        begin
            let hash = computeHashes(remId);
            for (Integer i = 0; i < valueOf(BLOOM_COUNTING_HASHES); i = i + 1)
            begin
                bf_down[hash[i]] = 1;
            end

            debugLog.record($format("    Bloom filter REMOVE input state, id=0x%x: %0d (%0d), %0d (%0d), %0d (%0d), %0d (%0d)",
                                    remId,
                                    hash[0], bf[hash[0]],
                                    hash[1], bf[hash[1]],
                                    hash[2], bf[hash[2]],
                                    hash[3], bf[hash[3]]));
        end

        // Pass the update vectors to the next rule (same cycle)
        updateBits.wset(tuple2(bf_up, bf_down));
    endrule


    (* fire_when_enabled *)
    rule updateFilter2 (True);
        //
        // Consume the result of updateFilter1 and update the Bloom filter.
        //

        if (updateBits.wget() matches tagged Valid {.bf_up, .bf_down})
        begin
            Vector#(nFilterBits, Bit#(nCounterBits)) bf_new;

            // A filter slot changes if only one of up and down is requested
            let bf_changes = bf_up ^ bf_down;

            for (Integer i = 0; i < valueOf(nFilterBits); i = i + 1)
            begin
                if (bf_changes[i] == 1)
                    // Position gets new value
                    bf_new[i] = bf[i] + ((bf_up[i] == 1) ? 1 : -1);
                else
                    // Position unchanged
                    bf_new[i] = bf[i];
            end
       
            bf <= bf_new;
        end
    endrule


    interface COUNTING_FILTER countingFilterIfc;
        method Action reset();
            bf <= replicate(0);
        endmethod


        method ActionValue#(Bool) insert(t_ENTRY newEntry);
            let hash = computeHashes(newEntry);

            //
            // Update counters for the hashes.  Compute two properties:
            //   all_set --  True iff all hashes were already set in the filter,
            //               indicating the index is already present.
            //   overflow -- True iff any counter would overflow.
            //

            Bool all_set = True;
            Bool overflow = False;

            debugLog.record($format("    Bloom filter INSERT input state, id=0x%x: %0d (%0d), %0d (%0d), %0d (%0d), %0d (%0d)",
                                    newEntry,
                                    hash[0], bf[hash[0]],
                                    hash[1], bf[hash[1]],
                                    hash[2], bf[hash[2]],
                                    hash[3], bf[hash[3]]));

            for (Integer i = 0; i < valueOf(BLOOM_COUNTING_HASHES); i = i + 1)
            begin
                let bucket = hash[i];

                all_set = all_set && (bf[bucket] != 0);

                let new_count = bf[bucket] + 1;
                overflow = overflow || (new_count == 0);

                if (new_count == 0)
                    debugLog.record($format("    Bloom filter bucket %0d overflow", bucket));
            end

            if (all_set || overflow)
            begin
                // Can't insert.  Only print insert FAIL message once.
                if (! isValid(lastFailMsg) || (pack(newEntry) != pack(validValue(lastFailMsg))))
                begin
                    lastFailMsg <= tagged Valid newEntry;
                    debugLog.record($format("    Bloom filter INSERT FAIL"));
                end

                return False;
            end
            else
            begin
                debugLog.record($format("    Bloom filter INSERT OK"));
                lastFailMsg <= tagged Invalid;
                insertVec.wset(hash);
                return True;
            end
        endmethod


        method Action remove(t_ENTRY oldEntry);
            removeId.wset(oldEntry);
        endmethod


        method Bool notSet(t_ENTRY entry);
            let hash = computeHashes(entry);

            Bool all_set = True;
            for (Integer i = 0; i < valueOf(BLOOM_COUNTING_HASHES); i = i + 1)
            begin
                let bucket = hash[i];
                all_set = all_set && (bf[bucket] != 0);
            end

            // Entry is busy iff all hash bits are set
            return ! all_set;
        endmethod
    endinterface
endmodule
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    bluespec.com Forum Index -> Designing with BSV's Rules, Interfaces, ... All times are GMT - 4 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum
bluespec.com topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group
Protected by Anti-Spam ACP