[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

580.0. "Chains in a "graph"" by 9712::DANTOWITZ (David .. DTN: 226-6957) Wed Sep 17 1986 13:30

	I have a set of N cells.  Each cell may be written to or read
	from many times.  The cells are accessed by operations.  An
	operation may read one or two cells and will write one cell.
	This problem involves a series of operations and a set of N
	cells.

	I am attempting to write an efficient algorithm to detect what
	I call "chains".  A chain is a series of operations that begins
	by reading a value from cell i, and writing to cell j; the next
	operation to access j MUST read it and write to k; the next
	operation to access k MUST read it and write to l, etc.  This
	continues until the cell i is written to.  Thus we see a chain
	of results: 

	             i -> j -> k -> ... -> i

	The simplest chain is an operation that reads from and writes to
	the same cell.  The goal of this algorithm is to detect ALL
	chains in a series of operations.  (In an efficient manner.)

	A chain does not have to involve consecutive operations, only
	operations that meet the above requirements.  Note for example
	that after j is read and a result written to k, j may be written
	over and this will not effect the nature of the chain.

	David
T.RTitleUserPersonal
Name
DateLines
580.1QuestionsCHOVAX::YOUNGI think we're all bozos on this BUS.Thu Sep 18 1986 23:0032
    Three questions:
    
    #1.
    
    >	by reading a value from cell i, and writing to cell j; the next
    >	operation to access j MUST read it and write to k; the next
    >	operation to access k MUST read it and write to l, etc.  This

    	Is this a requirement for a set of operations to be valid, or
    is it only a requirement for the valid formation of a chain?
    
    
    #2.
    
    	Does the following sequence:
    
    		1: (i,j) -> k
    		2:   (k) -> i
    		3:   (k) -> j
    
    					constitute 2 chains ( i(1)-k(2)-i,
    	and j(1)-k(2)-j ), 1 chain ( i(1)-k(2)-j(1)-k(2)-i ), or 0 chains?
    	(ie. just how does the 2 read, 1 write operation affect the
    	definition/construction of a chain?)
    
    
    #3.
    
    	What on earth is this for? (just curious B^) ).
    
    -- Barry
    
580.2Answers9712::DANTOWITZDavid .. DTN: 226-6957Fri Sep 19 1986 14:1174

    Three answers: (re .1)
    
    #1.
    
>>	by reading a value from cell i, and writing to cell j; the next
>>	operation to access j MUST read it and write to k; the next
>>	operation to access k MUST read it and write to l, etc.  This

>    	Is this a requirement for a set of operations to be valid, or
>    is it only a requirement for the valid formation of a chain?
    

	This is a requirement for a chain.  A set of operations may
 	have no chains at all.
    


    #2.
    
>    	Does the following sequence:
>    
>    		1: (i,j) -> k
>    		2:   (k) -> i
>    		3:   (k) -> j
>    
>    					constitute 2 chains ( i(1)-k(2)-i,
>    	and j(1)-k(2)-j ), 1 chain ( i(1)-k(2)-j(1)-k(2)-i ), or 0 chains?
>    	(i.e. just how does the 2 read, 1 write operation affect the
>    	definition/construction of a chain?)
    
    
	The above example has two chains (i(1)->k(2)->i and j(1)->k(3)->j).

	Let me propose a notation now:

	"x(A)->z" is to be interpreted as : 
	"Cell x is read by operation A and operation A writes cell z"

	Thus we may form a chain by appending "x(A)->z" and "z(B)->w"
	to form "x(A)->z(B)->w" IF there are no intermediate writes
	to cell z in between operation A and B.

	The following set of operations has the following chains:

             i(1)->k(3)->i, j(1)->k(4)->j, and h(5)-> h

    
    		1: (i,j) -> k
		2:   (k) -> h
    		3:   (k) -> i
    		4:   (k) -> j
	        5:   (h) -> h
                6:   (k) -> i


   #3.
    
>    	What on earth is this for? (just curious B^) ).
    

	This is part of the work being done for an instruction generation
	program.  The program generates sample sets of instructions and
        one of the useful pieces of information about a sequence of
  	instructions is the number of chains (as well as resource
	usage like memory & registers).  There are two straight-forward 
	algorithms that I've come up with (top-down and bottom-up)
	and on intuition the bottom-up seems better, but I haven't tested
	them yet.

	

    David
580.3Closed chains9712::DANTOWITZDavid .. DTN: 226-6957Mon Sep 22 1986 12:546
	A better term for these would be "Closed" chains, since
	a "simple" chain would merely reflect the flow of results
	from one operation to another.

	David
580.4More questions.CHOVAX::YOUNGI think we're all bozos on this BUS.Thu Sep 25 1986 16:3123
    I'm still working on this (not easy).
    
    Can you tell me a couple of things?
    
    	1)  What is the average number of instructions that you expect?
    
    	2)  What is the Maximum number of instructions (if any)?
    
    	3)  Is the address set to be a well defined numeric range, or
    	   is it to be an open range of symbolic identifiers?
    
    	4)  Ave & Max for number of unique addresses.
    
    	5)  What is the expected ratio of 1 read 1 write instructions
    	   to 2 read 1 write instructions?
    
    	6)  What kind of response times would you like/require for (1)
    	   and (2) ?
                                                                   2
    So far I have some working algorithims, but they look to be O(n )
    or O(n*a), where a=# addresses.
    
    -- Barry
580.5 ... 9712::DANTOWITZDavid .. DTN: 226-6957Thu Sep 25 1986 20:2941
    
    	1)  What is the average number of instructions that you expect?

	    4.5 for now.  Perhaps as high as 32.
    
    	2)  What is the Maximum number of instructions (if any)?

	    8 for now, perhaps up to 64.
    
    	3)  Is the address set to be a well defined numeric range, or
    	   is it to be an open range of symbolic identifiers?
    
           I am using a fixed set of 64 cells.

    	4)  Ave & Max for number of unique addresses.

           Average unique cells is 15.
    
    	5)  What is the expected ratio of 1 read 1 write instructions
    	   to 2 read 1 write instructions?
    
            25% have 1 read.  A small % read the same cell twice.


    	6)  What kind of response times would you like/require for (1)
    	   and (2) ?
                                                                   2
            Good question.  My work on this problem has been
	    slowed to a stop.  My guess is some pruning can be
	    done.

            My original intent was to see if there were any 
	    elegant solutions akin to matrix multiplication
	    etc.  When I get a sample algorithm running I 
            will post it here.


	Thanks for the effort.  Things are really busy here, but
	I intend to get back to this as ASAP.

	David
580.6Uh Oh.CHOVAX::YOUNGI think we're all bozos on this BUS.Tue Sep 30 1986 04:1438
    Uh, bad news Dave.
    
    It appears that there are certain pathological sequences of
    instructions that will cause an exponential number of circuits to
    be formed.  Finding, and deliniating all of them would likewise
    require exponential time (of course).
    
    Consider:
    
    		1:     (a1) -> b1
    		2:     (a1) -> c1
    		3:  (b1,c1) -> a2
    now repeat;
    		4:     (a2) -> b2
    		5:     (a2) -> c2
    		6:  (b2,c2) -> a3
    et cetera.
    
    Even this short sequence has at least four circuits (curious onlookers
    may amuse themselves by trying to find them all...).  Adding another
    three instructions like this will raise that to eight.
    
    In short:
                               (n/3)
    	Max_circuits (n)  ~=  2     
    
    For the stated maximum of 64 instructions could result in at least
    2^21 circuits (WARNING: Home viewers should NOT try this on their
    own computers).
    
    Of course no pratical algorithim would be interested in garbage
    results like this, but I can't seem to come up with a set of 
    limitations/revisions of the stated problem that eliminates all
    the garbage, keeps all the valuable possibilities, and is tractable.
    
    Any help?
    
    -- Barry