Remote Manipulation of Binary Decision Diagrams in a Client/Server Computing Environment

written by Gurmeet Singh Manku and Zhengyu Zhang

1. Project Goal

Decision Diagrams (BDDs) provide a useful data structure in manipulating boolean functions. BDD manipulation constitues the core operation in symbolic synthesis and verification applications (VIS, SMV, SIS). Many robust BDD packages have been developed in academia (CUDD, CMU, CAL). The explosive growth of the Internet has raised the interest in web-based computing model, e.g. WELD. In this project we want to explore the feasibility of a BDD server and the objective is to allow multiple users and various applications to concurrently use a generic BDD package over the web. Also we will explore various techniques to improve the computational efficiency upon .

2. Introduction

Whilewe realize that it is also necessary to retain the backward compatibility of the legacy EDA tools and applications. We not only want to make the legacy tools to work in the new environment, but we want to let these applications take maximum advantages the new environment. The common way of accomplishing this is to construct an object wrapper so that the encapsulated legacy application will possess the same properties as any other distributed objects in the client/server environment. In this project, we are going to demonstrate the feasibility of this kind of migration methodology.

The client is a process (program) that sends a message to a server process (program), requesting that the server perform a task (service). Client programs usually manage the user-interface portion of the application, validate data entered by the user, dispatch requests to server programs, and sometimes execute business logic. The client-based process is the front- end of the application that the user sees and interacts with. A server process (program) fulfills the client request by performing the task requested.

Server programs generally receive requests from client programs, execute database retrieval and updates, manage data integrity and dispatch responses to client requests. Sometimes server programs execute common or complex business logic. The server-based process "may" run on another machine on the network. This server could be the host operating system or network file server; the server is then provided both file system services and application services. Or in some cases, another desktop machine provides the application services. The server process acts as a software engine that manages shared resources such as databases, printers, communication links, or high powered-processors. The server process performs the back-end tasks that are common to similar applications.

With our approach, we recognize that BDDs are memory-intensive and occupy a significant fraction of the total computation time for an application. Therefore, a fast server with a large amount of main memory running the BDD package would provide the necessary processing power for client processes. By seperating an application according to the client/server model, users of such a tool would be given great flexibility, e.g. one could use light weight network computing devices to access the server. Here is the outline of our approach for this project:

Architecture Overview

The BDD operations are the center piece of many sythesis/verification tools. In a high level BDD program, functions from BDD packages are called to perform specific tasks and the following illustrates what a common program might look like:


/* initialize a BDD manager */
            Mgr  *bdd_manager_create(...); 
/* create  variables */
           var *bdd_var_create(mgr,v1,...);
/* And two variables just created */
           var *bdd_And (mgr, var *v1, var *v2);
/******************************************************/
Mgr *m;
var* v1,v2,...;
m = bdd_manager_create(...);
v1 = bdd_var_create(m,...);
v2 = bdd_var_create(m,...);
v3 = bdd_And(m,v1,v2);
v4 = bdd_AND(m,v3,v2);
v5 = bdd_OR(m,v2,v4);
...
bdd_manager_destroy(m);








In a client/server environment, a function call has to be intercepted and translated into a networking transaction. So we break the entire process into three parts and tackle each one seperately. The three parts are listed as follows:

                   interface            BDD daemon
      Java Front End <---> Client/Server <------> BDD processs  

Java Front End

Java front end interacts with the users. Ideally, the front end will be the java version of the synthesis/verification tools like VIS and SIS. The function calls to the local BDD package would have to be rewritten so that a socket connection must be initialized for the subsequent BDD operations. Since we would like to build upon the existing WELD infrastructure to the largest extent, we decide to use Francis Chan's Java client communication packages. To demonstrate this to the users, some applications involving BDD manipulations have to be developed in Java as well. (more detail later)

Client/Server

The client side has been taken care of, we are also looking for the possible implementation on server side. We need to create a daemon server that will folk processes. We will write the client using java.

BDD process

Once the processes are folked from server, we need mechanisms to keep track of each process so the data send across the network is not going to be misplaced into different BDD managers. The BDD process will compute the result and return the result to the server: the inter-application process is done using IPC (pipe(), exec()).

Here are sample code for each process:

while (message from pipe())
    {   m <-- get_message();
        switch(m->type)
         {
            MGR_GREATE:{mgr = bdd_mgr_create(m->param);
                        <write mgr to pipe>;
                        break;}
            VAR_CREATE:{var = bdd-var_create(m->para);
                        <write var to pipe>
                        break;}
            default:
         }
 }

Progress:

4-9

Gurmeet and I outlined utlined the entire plan and finalized some part of the implementation detail. This report was written up after our meeting.

4-14

Java interface - a preliminary version- was written.

4-15

Francis gave Charlie and me a brief introduction of what his code can do in a client/DB environment and we also discussed the possiblities of using the Java client for our client/server computing model. Some sample source code was put on-line by Francis. I need take a look at this code. Inventing a new format and parsing it to client was identified as the biggest challenge. Charlie(Gurmeet) also would write some short notes on his thoughts about the server+daemon implementation. A request to meet with Mark concerning the client program was also scheduled.

4-17

Read Mark's C++ server code

Read Charlie's Socket programming book

4-26

finish the topologic sorting on the client side.

4-27

modified the server software (start) and defined a set of protocol for operation encoding and decoding

4-28

Results:

Performance

Conclusion:

Not finished yet.


last updated 4/15/97