From README.md
MiniTri is a proxy for a class of triangle based data analytics (Mantevo). This simple code is a self-contained piece of C++ software that uses triangle enumeration with a calculation of specific vertex and edge properties. Key uses related to miniTri include dense subgraph detection, characterizing graphs, improving community detection, and generating graphs. Related applications exist in cyber security, intelligence, and functional biology. miniTri attempts to be more application relevant than standard data analytics benchmarks such as Graph 500.
Problem Size and Run Information
Running miniTri requires a graph file with an option to specify its format: [fileformat ={MM || Bin}]
One location for to download a graph file is at http://graphchallenge.mit.edu/data-sets.
The problem size is determined by the details of the input graph.
Analysis
Build and Run Information
Compiler = 'clang 5.0.1'
Build_Flags = '-g -O3 -march=native -DNDEBUG -fopenmp -std=c++11'
Run_Parameters = 'email-Enron_adj.mmio 10 [# Threads]'
Scaling
addNZ( )
| 1 (67.5%) | 1.2 | 1.7% | 70.6% | 9.9% | 0.45 | 3.5% | 3.3% | 0.7% |
| 72 (65.7%) | 0.45 | 1.6% | 67.0% | 0.0% | 0.13 | 2.0% | 1.8% | 0.0% |
627 int addNZ(std::map<int,std::list<int> > &nzMap,int col, int elemToAdd)
628 {
629 std::map<int,std::list<int> >::iterator it;
630
631 it = nzMap.find(col);
632
633 //////////////////////////////////////
634 //If columns match, no additional nz, add element to end of list
635 //////////////////////////////////////
636 if(it != nzMap.end())
637 {
638 (*it).second.push_back(elemToAdd);
639 return 0;
640 }
641
642 std::list<int> newList;
643 newList.push_back(elemToAdd);
644 nzMap.insert(std::pair<int,std::list<int> >(col, newList));
645 return 1;
646 }
Most of the work of the kernel is done in the Standard Template Library
| STL function | |
|---|---|
insert() |
26.6% |
push_back() |
15.7% |
find() |
9.4% |
list construction |
9.6% |
list deconstruction |
2.3% |
computeKCounts
| Threads (Time) | Inst/Cycle per Core | L1 DC Miss % | L2 DC Miss % | L3 Miss % | L1 Loads/Cycle per Core | L2 B/W Used | L3 B/W Used | DRAM B/W Used |
|---|---|---|---|---|---|---|---|---|
| 1 (1.7%) | 0.79 | 9.8% | 44.6% | 0.0% | 0.16 | 5.4% | 3.2% | 0.0% |
| 72 (4.2%) | 0.18 | 4.4% | 65.0% | 0.0% | 0.06 | 1.7% | 1.5% | 0.0% |
668 #pragma omp for schedule(dynamic,mBlockSize)
669 for (int rownum=0; rownum<m; rownum++)
670 {
671 for(int nzIdx=0; nzIdx<nnzInRow[rownum]; nzIdx++)
672 {
673 int v1 = rownum;
674 int v2 = vals[rownum][nzIdx];
675 int v3 = vals2[rownum][nzIdx];
676
677 // Removes redundant triangles
678 if(v1>v2 && v1>v3)
679 {
680
681 /////////////////////////////////////////////////////////////////////////
682 // Find tvMin
683 /////////////////////////////////////////////////////////////////////////
684 unsigned int tvMin = std::min(std::min(vTriDegrees[v1],vTriDegrees[v2]),
vTriDegrees[v3]);
685 /////////////////////////////////////////////////////////////////////////
686
687 /////////////////////////////////////////////////////////////////////////
688 // Find teMin
689 /////////////////////////////////////////////////////////////////////////
690
691 // I believe that v2<v3 by construction
692 int e1,e2,e3;
693 if(v2<v3)
694 {
695 e1 = edgeInds.find(v2)->second.find(v3)->second;
696 e2 = edgeInds.find(v2)->second.find(v1)->second;
697 e3 = edgeInds.find(v3)->second.find(v1)->second;
698 }
699 else
700 {
701 e1 = edgeInds.find(v3)->second.find(v2)->second;
702 e2 = edgeInds.find(v3)->second.find(v1)->second;
703 e3 = edgeInds.find(v2)->second.find(v1)->second;
704 }
705
706 unsigned int teMin = std::min(std::min(eTriDegrees[e1],eTriDegrees[e2]),
eTriDegrees[e3]);
707 /////////////////////////////////////////////////////////////////////////
708
709 /////////////////////////////////////////////////////////////////////////
710 // Determine k count for triangle
711 /////////////////////////////////////////////////////////////////////////
712 unsigned int maxK=3;
713 for(unsigned int k=3; k<kCounts.size(); k++)
714 {
715 if(tvMin >= choose2(k-1) && teMin >= k-2)
716 {
717 maxK = k;
718 }
719 else
720 {
721 break;
722 }
723 }
724 localK[maxK]++;
725 /////////////////////////////////////////////////////////////////////////
726 }
727 }
728 } // end loop over rows