[TECH] Ideas for Optimizing Design pattern implementations with Stack Collapsing

One major drawback I guess with all these object oriented systems I guess is performance, since people write the code so that its extensible it always ends up creating deep stack sizes, recently I was looking into
(Jmol) this structure visualization tool supports several input format descriptions for the structures (pdb,cif,molxyz….). This is how they hide format details from the display code
JmolAdapter (abstract class)
==> SmarterJmolAdapter (this contains
a interface called AtomSetCollection ). So depending on the input file
we have several AtomSetCollection readers like PdbAtomSetCollection etc…

Although I came to a conclusion that to implement the structural alignment algorithm into Jmol, I need to implement this AtomSetCollection which structurally aligns the protein structures, but I guess there are several draw backs of the implementation of object oriented java implementation, the cost of creating an
extensible design does not come for free it comes at the cost of performance, I found that a simple command execution could end up creating a stack size of 32 this is what
concerns me is there a way we can collapse the stack when we know that the intermediate functions on the stack are just delegating the call to the actual instance, I guess this STACK COLLAPSING technique can always be applied when ever
the Adapter design pattern is used. For example see the below stack of size 32,
its not doing any thing great its just opening a new script file, because of the
way the code is written (use of design patterns) the stack size seem to increase
a lot and ULTIMATELY ALL THESE PATTERNS ARE JUST DELEGATING A FUNCTION CALL TO
TO FUNCTION ON TOP OF THE STACK, I’m think of ways to improve the delegation since
at each level of the stack you are doing a look up and it increases linearly with
the size of the stack.

  [1] org.jmol.viewer.ScriptManager.addScript (ScriptManager.java:69)
  [2] org.jmol.viewer.ScriptManager.addScript (ScriptManager.java:52)
  [3] org.jmol.viewer.Viewer.evalStringQuiet (Viewer.java:3,152)
  [4] org.jmol.viewer.Viewer.evalString (Viewer.java:3,119)
  [5] org.jmol.viewer.Viewer.openFile (Viewer.java:1,379)
  [6] org.openscience.jmol.app.Jmol$OpenAction.actionPerformed (Jmol.java:1,435)
  [7] javax.swing.AbstractButton.fireActionPerformed (AbstractButton.java:1,849)
  [8] javax.swing.AbstractButton$Handler.actionPerformed (AbstractButton.java:2,169)
  [9] javax.swing.DefaultButtonModel.fireActionPerformed (DefaultButtonModel.java:420)
  [10] javax.swing.DefaultButtonModel.setPressed (DefaultButtonModel.java:258)
  [11] javax.swing.AbstractButton.doClick (AbstractButton.java:302)
  [12] javax.swing.plaf.basic.BasicMenuItemUI.doClick (BasicMenuItemUI.java:1,051)
  [13] javax.swing.plaf.basic.BasicMenuItemUI$Handler.mouseReleased (BasicMenuItemUI.java:1,092)
  [14] java.awt.Component.processMouseEvent (Component.java:5,517)
  [15] javax.swing.JComponent.processMouseEvent (JComponent.java:3,135)
  [16] java.awt.Component.processEvent (Component.java:5,282)
  [17] java.awt.Container.processEvent (Container.java:1,966)
  [18] java.awt.Component.dispatchEventImpl (Component.java:3,984)
  [19] java.awt.Container.dispatchEventImpl (Container.java:2,024)
  [20] java.awt.Component.dispatchEvent (Component.java:3,819)
  [21] java.awt.LightweightDispatcher.retargetMouseEvent (Container.java:4,212)
  [22] java.awt.LightweightDispatcher.processMouseEvent (Container.java:3,892)
  [23] java.awt.LightweightDispatcher.dispatchEvent (Container.java:3,822)
  [24] java.awt.Container.dispatchEventImpl (Container.java:2,010)
  [25] java.awt.Window.dispatchEventImpl (Window.java:1,791)
  [26] java.awt.Component.dispatchEvent (Component.java:3,819)
  [27] java.awt.EventQueue.dispatchEvent (EventQueue.java:463)
  [28] java.awt.EventDispatchThread.pumpOneEventForHierarchy (EventDispatchThread.java:242)
  [29] java.awt.EventDispatchThread.pumpEventsForHierarchy (EventDispatchThread.java:163)
  [30] java.awt.EventDispatchThread.pumpEvents (EventDispatchThread.java:157)
  [31] java.awt.EventDispatchThread.pumpEvents (EventDispatchThread.java:149)
  [32] java.awt.EventDispatchThread.run (EventDispatchThread.java:110)

[TECH] Association rules of by Data Mining (TM Algorithm) on Cancer Data.

I have datamined the Cancer data at http://breastscreening.cancer.gov/rfdataset/ using the TM(Transaction Mapping) and FP-Growth algorithm, this is what I have done
to mine the association rules.

1. Randomly partition the data into two parts, I partitioned the
data into part1 of size = 148458 records, part2 of
size = 153897.


2. Used the part1 (148458 records) and found association rules of
support >=0.4 and
confidence >=0.4 , I got 72 rules from this.

3. For each of the rule (in step 2) I found the support and confidence
of each of the rules in
part2, it looks like the support and confidence is close to the
support and confidence in
training data (part1).

The 72 rules of step1 [
http://www.engr.uconn.edu/~vkk06001/CancerDataMining/rules.txt ]

Support and Confidence of each of this rules in part2
[http://www.engr.uconn.edu/~vkk06001/CancerDataMining/training_result.txt ]

I have made the rules human readable removing all the encoding please
see the rules
[
http://www.engr.uconn.edu/~vkk06001/CancerDataMining/human_readable.txt ]

These are in the following format
==============RULE:1=================
SUP:0.402 ,CONF:0.412,TRAIN_SUP:0.404,TRAIN_CONF:0.414
{
Diagnosis of invasive breast cancer within one year of the index
screening mammogram = no,
}
IMPLIES ===>
{
Diagnosis of invasive or ductal carcinoma in situ breast cancer within
one year of the index screening mammogram = no,
menopaus = postmenopausal or age>=55,
hispanic = no,
}
==============RULE:2=================

SUP indicates support of this rule in part2 , CONF indicates confidence of this
rule in part2, TRAIN_SUP indicates the support of this rule in part1 and
TRAIN_CONF indicates the confidence of this rule in part1.

These rules may not make any sense for me but it might make sense for a cancer doctor. There are several useful perl programs for people who want to do some
datamining please feel free to use them http://www.engr.uconn.edu/~vkk06001/CancerDataMining
, let me know if you have any questions.

[TECH] An observation to merge upper convex hulls in O(log(n)) time rather than O(log^2(n)).

The well known divide and conquer algorithm for finding convex hull for a given set of points, needs to merge smaller hulls H_1 and H_2 for doing this merge the algorithm uses lemma 3.2 (in Book Fundamentals of Computer Algorithms). This lemma essentially finds the tangent line (u,v) in O(log^2(n)) time.

We can in fact merge the hulls in more efficient manner, the observation is based on the fact that any point with maximum y-coordinate should definitely be on the hull. Let p1 and p2 be the points in hulls H_1 and H_2 with maximum y-coordinate, then we can safely state that either p1 or p2 will be on the combined hull of H_1 and H_2, we can determine which of these two points lie on the merged hull by comparing the y-coordinates of p1,p2. Among these two the point with maximum y-coordinate will definitely be on the merged hull so one end of the tangent line (u,v) is fixed, the other end of the tangent line can be probed in O(log(n)) time, this basically saves the extra O(log(n)) time which is spent previously in lemma 3.2 for finding the other end of tangent in H_2

[TECH] Hanging simulation..

I came across a interesting problem in which the entire simulation
was hanging just because of an extra non-sensitive always block , in
the verilog code the statement “always dummy_reg = in;” was causing
both VCS and NC-VERILOG hang. Theoretically speaking irrespective of
what I do in my design the simulation should stop after 500 steps
because I have a “#500 $finish” in the initial block of the module
“TestHangMux”, although I got around this problem by removing the
“dummy_reg” totally in the multiplexer, but I still don’t understand
why the simulation was hanging irrespective of the “#500 $finish” statement,
is it because we have multiple non-sensitive “always” statement? the LRM(Language
Reference Manual) says that all the “always” blocks execute in parallel just
like parallel processors in that that the statement “#500 $finish” should have
executed in parallel and stop the simulation but why it hangs?

===================================
module HangMux(in,sel,out);
input [1:0]in;
input sel; output out;
reg [1:0]dummy_reg;
reg out;

always @(sel) begin
    case(sel)
        0: out = dummy_reg[0];
        1: out = dummy_reg[1];
    endcase
end

always dummy_reg = in;

endmodule

module TestHangMux(out_net);
output out_net;
wire out_net;
reg [1:0]in_reg;
reg sel;

initial begin
 in_reg = 2'b01;
 sel = 0;
#500 $finish;
end

always begin
#10 sel = ~sel;
end

HangMux hang_me (in_reg,sel,out_net);
endmodule
==============================

[TECH] Finding frequent itemsets faster than FP-Growth algorithm

I wanted to implement my prime-number mapping intersection algorithm into the TM(Transaction Mapping) Algorithm, I got the FP-Tree implementation from PERL FP Tree and was trying to test this on a data of around 300,000 records, it works till 10,000 records
with support and confidence of 0.8 and 0.9 and fails if the number of records > 20,000. I’m not sure if its a perl bug but the following code which is the cause of the problem seems difficult to understand

===================================================================
@association_rules = map $_->[0], (sort {$b->[1]  $a->[1]}
      (map [$_, $_->confidence], @association_rules));
===================================================================

I tried to bless the reference $_ but it did’nt work. The following is the
error it gives.

[vamsik@abadon Tree-FP-0.04]$ !perl
perl test_vamsi.pl
Setting support
Mining rules...
Can't call method "confidence" on an undefined value at /usr/lib/perl5/site_perl/5.8.8/Tree/FP.pm line 397,  line 20001.

I need to fix this and send it to the FPTree maintainer tomorrow. I guess
its really a issue to implement the FPTree in perl because of the speed and
time especially when the algorithm need to work on huge data just in my
case. A good idea is to re-write FPTree in C and extend TM based on that
and compare the results.

[TECH] why is ((unsigned long)a_ptr+(unsigned long)b_int) not equals (a_ptr+(unsigned long)b_int)

I was looking at some code today on SGI super computer, and wanted
to make sure that there are no 32-64 bit problems in the code since
SGI was super computer. I found the following thing to be interesting

((unsigned long)a_ptr+(unsigned long)b_int)!=
          (a_ptr+(unsigned long)b_int)

That is if I cast both the operands of binary + to (unsigned long)
the value I get from that addition is different from if I cast
just one operand of binary + to (unsigned long), whats the compiler
doing here? since if both the operands to binary + are unsigned long
and the value(no.of bits) could be larger than sizeof(unsigned long)
is it the reason why I get different values here?, I couldn’t find
this in FAQ.

[TECH] Verilog incompatabilities between ‘ncverilog’ and ‘vcs’

Thanksgiving vacation may be fun for some but its really not fun if your IT department
is taking a break, our Synopsys License server has been down for last few days all my
emails are vain no one responds. I used ‘vcs’ to compile all my verilog code all these
days, now I’m helpless…..how can we solve this problem.
I want to get some synthesis metrics for the Sequence Alignment design, although Synopsys License server is down looks like the Cadence License server is up . Thats
good news but whats equivalent to ‘vcs’ in Cadence….’NCVERILOG’ I found ‘ncverilog’
and try to compile all my design modules now the in-compatibility, NC-Verilog don’t like to see any thing in the module description until all the port list is filled up,but vcs scans the code of the entire declaration list before checking if the port list is filled up (I guess thats the way it should be the algorithm should be very general). I like ‘vcs’ and not impressed by ‘NC-Verilog’ but unfortunately I have to live with it for few more days, by porting my verilog code…sounds crazy I have ported code on machines different processors but the way these compilers are build is
really crazy….

[TECH] Iso-spectral and Non-Isomorphic Graphs (PINGS)

Having the same spectrum for the adjacency matrix is a Necessary but not
sufficient condition for Graph Isomorphism, our recent algorithmic result states a conjecture that every graph is characterized by its Family of Spectra, rather than
Spectrum itself.

I have been doing some work on efficient algorithms for generating PINGS (Pair of
Isospectral and Non-Isomorphic Graphs), I wrote a program which can search for PINGS
in a very efficient manner, I found some interesting results there are no PINGS
for n=2,3,4 for n=5 we have one PING (see the picture) it happens that its the only PING for n=5 it has a symmetric spectrum of {-2,0,0,2}. Also I found a very interesting result that there cannot be more than two INGS(Iso-Spectral
and non-isomorphic graphs) which share the same spectrum so if INGS exists they
exist as PINGS, I was curious if they exist something like XINGS X=P or T or …
but it happens its just P (only a pair). There are 5 PINGS for n=6 for n=7 there
are 55 PINGS see the list at
http://trinity.engr.uconn.edu/~vamsik/n.7.

[TECH] Design of my first chip (A sequence Aligner O(n) space implementation)

Designing hardware is totally different from writing software, writing verilog code
is totally different from writing software ‘C’ programs, often a software engineer tries to solve the problems using loops,arrays etc.. unfortunately implementing the same algorithm in hardware is totally different. I had my experience in designing a chip (verilog code) for finding edit distance between two strings this has a well known
O(n^2) dynamic programming based algorithm. Now the trick is how do you create a hardware which realizes the two for loops in the O(n^2) algorithm, after quite a bit of
thinking I came up with a solution which involves just SHIFTERS,MULTIPLEXERS and ADDERS. I’m not aware of any such hardware implementation of edit distance algorithm till now…I’m tempted to share my design diagram on the blog but I cannot do it until it gets published some where….

My design flow is as follows (verilog)->vcs; (libs+verilog)->Design Compiler; and I will use cadence virtuso (ICFB) for my placement and routing and also extraction; Will use HSPICE/Nanosim and spectre for postlayout simulation.

[TECH] A simple O(n^2) time algorithm to construct the Ultra-metric trees.

Given a matrix ‘D’ which is symmetric an Ultra-metric tree ‘T’ is a binary
tree with internal nodes corresponding to D(i,j) and leaves corresponding to
rows in the matrix ‘D’, and a path from the root to the leaf must be strictly decreasing (Ultra-metric tree). Also D(i,j) is the lowest common ancestor for
‘i’ and ‘j’.
The problem is given ‘D’ we need to figure out corresponding ‘T’.

The well know fact about the Ultra-metric trees is that if
we take any 3 leaves i,j,k the maximum is not unique (e.x D(i,j)=5,
D(j,k)=6,D(i,k)=5) we have D(i,j) and D(i,k) having same value.
How do we test if D is Ultra-metric?

• A trivial solution is O(n^3).
• The Errata shows construction of Ultra-metric trees in O(n^2) and asks a question if we can
  check for the Ultra-metric property in O(n^2) ? which my next item answers affirmatively.

• My observation is we can partition the leaves of the ultra-metric tree with out
  any need of building a complete weighted graph as in Gusfields solution, one fact is that every row in D is going to have a maximum (global) we don’t need to spend O(n^2) (comparing all the elements in the matrix D) to find one. The algorithm below we perform such a check if an ultra-metric tree exists and also builds one.

  
  L = {1,2,....n};
  UltraMetricPartition(L){
   i = select_a_random_element_in(L) ;
   max = find_max(D(i,*)); /*Takes linear time*/
   /*max = D(i,q) && q should be in L*/
   Part_q = {};
   Part_i = {};
   foreach(j in L){
      if(j!=i){
          if(D(j,i)<=max && D(j,q)==max){
               Part_i += {j};
          }else if(D(j,q)<=max && D(j,i)==max){
               Part_q += {j};
          }else{
             printf("D is not ultra-metric");
             return 0;
          }
      }
   }
   UltraMetricPartition(Part_i);
   UltraMetricPartition(Part_q);
  
  }
  
  

Running time would be T(n) = T(n-k) + T(k) + O(n), clearly its quadratic O(n^2).