* Re: [Caml-list] hypergraph partitioning algorithm ?
2010-06-01 16:45 ` Pietro Abate
@ 2010-06-01 17:05 ` Eray Ozkural
2010-06-01 18:52 ` Hugo Ferreira
1 sibling, 0 replies; 5+ messages in thread
From: Eray Ozkural @ 2010-06-01 17:05 UTC (permalink / raw)
To: Pietro Abate; +Cc: caml-list
Hi there,
Writing from mobile sorry for top posting. Partitioning a binary
decision diagram sounds right.
What I meant was an efficient implementation isn't easy and FM is only
part of the code. You'll be better off calling a multi level
hypergraph partitioning package like patoh or hmetis. It can take
several months to write one from scratch and make it run fast.
Cheers,
--
Eray Ozkural
http://myspace.com/arizanesil
On Jun 1, 2010, at 7:45 PM, Pietro Abate <Pietro.Abate@pps.jussieu.fr>
wrote:
> Hi. Deliberately going of topic...
>
> On Tue, Jun 01, 2010 at 07:21:07PM +0300, Eray Ozkural wrote:
>> Those are not very often implemented, and no there is none that I can
>> think of, at least freely so. However, I was actually planning on
>> implementing one, adapting some of our efficient algorithms.
>
> I'm far to be an expert on the field and I'd appreciate a bit of
> guidance...
>
> I was under the impression the hypergraph partitioning is the leading
> strategy to reduce the size of a BDD. When dealing with real size
> problems, finding a suitable order to work with BDDs is essential.
> Last
> week I've implemented an heuristic (FORCE) to derive a static ordering
> from my graph, but I then discovered that the bdd package I'm using
> (buddy bdd) deals pretty badly with static ordering taking a cubic
> time
> on the # of variables to set up a bdd with this order.
>
> The other option I have is to partition the graph in clusters and then
> use the buddy dynamic ordering that "apparently' works well ... To
> cut a
> long story short, this is what led me to hypergraph partitioning. Now
> you are saying that they are not often implemented and I'm wondering
> if
> I'm completely off track here and there are other heuristics to
> compute
> a suitable block order and therefore reduce the size of a bdd ...
> MINCE
> for example uses hypergraph partitioning in order to find a suitable
> variable ordering ...
>
> thanks !
>
> pietro
>
>>
>> On Tue, Jun 1, 2010 at 5:56 PM, Pietro Abate
>> <Pietro.Abate@pps.jussieu.fr> wrote:
>>> Hello,
>>>
>>> Do you know of any implementation of the Fiduccia-Mattheyses
>>> algorithm
>>> or other hypergraph partitioning / clustering algorithms in ocaml ?
>>>
>>> There are two c++ libraries (GTL and scotch) that implement these
>>> algorithms, but no binding to ocaml afaik...
>>>
>>> thanks !
>>> p
>>>
>>> --
>>> ----
>>> http://en.wikipedia.org/wiki/Posting_style
>>>
>>> _______________________________________________
>>> Caml-list mailing list. Subscription management:
>>> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
>>> Archives: http://caml.inria.fr
>>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>>
>>
>>
>>
>> --
>> Eray Ozkural, PhD candidate. Comp. Sci. Dept., Bilkent University,
>> Ankara
>> http://groups.yahoo.com/group/ai-philosophy
>> http://myspace.com/arizanesil http://myspace.com/malfunct
>
> --
> ----
> http://en.wikipedia.org/wiki/Posting_style
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [Caml-list] hypergraph partitioning algorithm ?
2010-06-01 16:45 ` Pietro Abate
2010-06-01 17:05 ` Eray Ozkural
@ 2010-06-01 18:52 ` Hugo Ferreira
1 sibling, 0 replies; 5+ messages in thread
From: Hugo Ferreira @ 2010-06-01 18:52 UTC (permalink / raw)
To: Pietro Abate; +Cc: caml-list
Pietro,
Pietro Abate wrote:
> Hi. Deliberately going of topic...
>
> On Tue, Jun 01, 2010 at 07:21:07PM +0300, Eray Ozkural wrote:
>> Those are not very often implemented, and no there is none that I can
>> think of, at least freely so. However, I was actually planning on
>> implementing one, adapting some of our efficient algorithms.
>
> I'm far to be an expert on the field and I'd appreciate a bit of
> guidance...
>
> I was under the impression the hypergraph partitioning is the leading
> strategy to reduce the size of a BDD. When dealing with real size
> problems, finding a suitable order to work with BDDs is essential. Last
> week I've implemented an heuristic (FORCE) to derive a static ordering
> from my graph, but I then discovered that the bdd package I'm using
> (buddy bdd) deals pretty badly with static ordering taking a cubic time
> on the # of variables to set up a bdd with this order.
>
> The other option I have is to partition the graph in clusters and then
> use the buddy dynamic ordering that "apparently' works well ... To cut a
> long story short, this is what led me to hypergraph partitioning. Now
> you are saying that they are not often implemented and I'm wondering if
> I'm completely off track here and there are other heuristics to compute
> a suitable block order and therefore reduce the size of a bdd ... MINCE
> for example uses hypergraph partitioning in order to find a suitable
> variable ordering ...
>
I may not have understood your issue correctly but have you considered
using the CUDD BDD package [1]? It provides a means to reorder the
variables and thereby reduce the BDD size. If I recall correctly you
could do this manually or automatically.
In order to use the library you can use the MlCuDDIDL library [2]. Last
I used it the library had been updated and it seemed to work nicely
with large BDDs (nearly 2 Gbytes). (At the time the author Bertrand
Jeannet took the time to look into the issues and made some
changes).
HTHs,
Hugo F.
[1] http://vlsi.colorado.edu/~fabio/CUDD/cuddIntro.html
[2] http://pop-art.inrialpes.fr/~bjeannet/mlxxxidl-forge/
> thanks !
>
> pietro
>
>> On Tue, Jun 1, 2010 at 5:56 PM, Pietro Abate
>> <Pietro.Abate@pps.jussieu.fr> wrote:
>>> Hello,
>>>
>>> Do you know of any implementation of the Fiduccia-Mattheyses algorithm
>>> or other hypergraph partitioning / clustering algorithms in ocaml ?
>>>
>>> There are two c++ libraries (GTL and scotch) that implement these
>>> algorithms, but no binding to ocaml afaik...
>>>
>>> thanks !
>>> p
>>>
>>> --
>>> ----
>>> http://en.wikipedia.org/wiki/Posting_style
>>>
>>> _______________________________________________
>>> Caml-list mailing list. Subscription management:
>>> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
>>> Archives: http://caml.inria.fr
>>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>>
>>
>>
>> --
>> Eray Ozkural, PhD candidate. Comp. Sci. Dept., Bilkent University, Ankara
>> http://groups.yahoo.com/group/ai-philosophy
>> http://myspace.com/arizanesil http://myspace.com/malfunct
>
^ permalink raw reply [flat|nested] 5+ messages in thread