blackwiki - user contributions [en]

File:Omphalos.png

2012-05-18T22:30:58Z

Dank: uploaded a new version of "File:Omphalos.png"

Omphalos: Network Dominance.

Dot

2012-05-13T22:20:44Z

Dank: /* PNG */

==SVG==
* graphviz tools generate svg via -Tsvg
* [http://github.com/vidarh/diagram-tools notugly] is some XSL to beautify dot's SVG output
==Examples==
Generated using Graphviz 2.20.2 and postprocessing via <tt>xsltproc</tt> and [http://github.com/vidarh/diagram-tools notugly]. I hand-wrote the dot sources.
===Packed Record===
[[Image:Opteron.svg|thumb|right|alt="Dot SVG example (packed record)"|A packed record-type node (click to enlarge)]]
<pre>digraph G {
subgraph clusterOpteron {
label="Quad-Core Opteron"
node [shape=record];
struct3 [label="{ {C0|C1|C2|C3}|{L1/L2|L1/L2|L1/L2|L1/L2}|SRI\
(SysReq Interface)|<xbar>XBAR (Crossbar Switch)|{MCH|ncHT-HB|HT0|HT1}}"];
}
} </pre>

===Rectilinear arrangement A===
[[Image:Deneb.svg|thumb|right|alt="Dot SVG example (rectilinear)"|A rectilinear graph (click to enlarge)]]
<pre>digraph G {
subgraph clusterOpteronNUMA {
label = "2x 'Deneb' Phenom II X4 910 (45nm, AM3). 8 threads."
Deneb0->Deneb1 [dir="both" label="2GHz 16-bit bidir\n8GB/s HyperTransport 3.0" color="blue"]
DDR0 -> Deneb0 [dir="both" color="lightblue"]
DDR1 -> Deneb1 [dir="both" color="lightblue"]
HostBus -> Deneb0 [dir="both" color="darkgreen"]
HostBus -> Deneb1 [dir="both" color="darkgreen"]
{ rank=same; Deneb0 Deneb1 }
{ rank=same; DDR0 DDR1 }
Deneb0 [style=filled fillcolor=steelblue shape=box]
Deneb1 [style=filled fillcolor=steelblue shape=box]
DDR0 [style=filled fillcolor=grey shape=invhouse]
DDR1 [style=filled fillcolor=grey shape=invhouse]
HostBus [style=filled fillcolor=green shape=Msquare]
}
}</pre>

===Rectilinear arrangement B===
[[Image:Nehalem.svg|thumb|right|alt="Dot SVG example (rectilinear)"|A rectilinear graph (click to enlarge)]]
<pre>digraph G {
nodesep="1"
subgraph clusterNehalemSMP {
DDR0 -> Nehalem0 [dir="both" color="lightblue"]
DDR0 -> Nehalem1 [dir="both" color="lightblue"]
Nehalem0->Nehalem1 [dir="both" label="25.6GB/s QuickPath" color="blue"]
subgraph clusterNehalemSMP0 {
label="DRAM may or may not be shared.";
style=filled;
color=lightgrey;
{ rank=same; DDR0 }
{ rank=same; Nehalem0 Nehalem1 }
}
Nehalem2->Nehalem3 [dir="both" label="25.6GB/s QuickPath" color="blue"]
Nehalem2 -> DDR1 [dir="both" color="lightblue"]
Nehalem3 -> DDR1 [dir="both" color="lightblue"]
subgraph clusterNehalemSMP1 {
labelloc="b";
label="Each package gets its own MCH and L3 cache,\neach core its own (split) L1 and (unified) L2.";
style=filled;
color=lightgrey;
{ rank=same; Nehalem2 Nehalem3 }
{ rank=same; DDR1 }
}
label = "4x 'Nehalem-EP' E5520 HT Core i7 (45nm LGA1336). 32 threads."
Nehalem1->Nehalem2 [dir="both" color="blue"]
Nehalem3->Nehalem0 [dir="both" color="blue"]
Nehalem0->HostBus [dir="both" color="darkgreen"]
Nehalem1->HostBus [dir="both" color="darkgreen"]
HostBus->Nehalem2 [dir="both" color="darkgreen"]
HostBus->Nehalem3 [dir="both" color="darkgreen"]
Nehalem0 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
Nehalem1 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
Nehalem2 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
Nehalem3 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
DDR0 [style=filled fillcolor=grey shape=invtrapezium]
DDR1 [style=filled fillcolor=grey shape=trapezium]
HostBus [style=filled fillcolor=green shape=Msquare]
}
} </pre>
===Large flow===
[[Image:libtorque.svg|thumb|right|alt="DOT SVG example (large flow)"|A large flow (click to enlarge)]]
<pre>digraph G {
nodesep="0.5"
subgraph clusterPrime {
labelloc="b";
compound="true"
subgraph clusterKernel {
label="Kernelspace (Linux epoll, FreeBSD kqueue, etc...)"
style=filled;
color=cadetblue;
wqueue0 [style=filled fillcolor=steelblue shape=Mdiamond]
wqueueN [style=filled fillcolor=steelblue shape=Mdiamond]
wqueue0 -> nics [dir=both]
nics [style="filled,diagonals" fillcolor=greenyellow label="Devices/IPC"]
nics -> wqueueN [dir=both]
{ rank=same; wqueue0 wqueueN nics }
}
subgraph clusterUser {
label="Userspace (libtorque-enabled process)";
style=filled;
color=gold;
evqueueN [style="diagonals,filled" fillcolor=mediumpurple shape=invtrapezium group="evq"]
evqueue0 [style="diagonals,filled" fillcolor=mediumpurple shape=invtrapezium group="evq"]
wqueue0 -> evqueue0 [dir=both style=bold color="blue:purple"]
wqueueN -> evqueueN [dir=both style=bold color="blue:purple"]
evqueue0 -> evqueueN [label="About sqrt(cpus) evqueues, usually" dir=both style=dotted color=maroon]
API -> evqueue0 [style=bold color=purple]
API -> evqueueN [style=bold color=purple]
API [style=filled fillcolor=green shape=box group="evq"];
{ rank=same; evqueue0 evqueueN }
node [shape=record];
thr0 [label="<t0>T0|<t1>T1|<t2>T2|<tN>TN"];
thrN [label="<t0>T0|<t1>T1|<t2>T2|<tN>TN"];
color=red;
evqueue0 -> thr0:t0 [color=blue]
evqueue0 -> thr0:t1 [color=blue]
evqueue0 -> thr0:t2 [color=blue]
evqueue0 -> thr0:tN [color=blue]
evqueueN -> thrN:t0 [color=blue]
evqueueN -> thrN:t1 [color=blue]
evqueueN -> thrN:t2 [color=blue]
evqueueN -> thrN:tN [color=blue]
{ rank=same; thr0 thrN }
thr0 -> sigtable [color=lightblue style=bold]
thr0 -> fdtable [color=lightblue style=bold]
thr0 -> twheel [color=lightblue style=bold]
thrN -> sigtable [color=lightblue style=bold]
thrN -> fdtable [color=lightblue style=bold]
thrN -> twheel [color=lightblue style=bold]
fdtable [style=filled fillcolor=lightgreen shape=box label="fd monads\n(array)"]
twheel [style=filled fillcolor=lightgreen shape=box label="timer monads\n(hwheel or array)"]
sigtable [style=filled fillcolor=lightgreen shape=box label="sig monads\n(array)"]
sigtable -> fdtable [color=lightblue label="AIO"]
fdtable -> buf [color=lightblue]
fdtable -> dnsssl [color=lightblue]
twheel -> dnsssl [color=lightblue]
buf -> API
{ rank=same; sigtable fdtable twheel }
dnsssl -> API
dnsssl [style=filled fillcolor=lightgreen shape=box label="DNS, SSL/TLS\n(adns, OpenSSL)"]
buf [style=filled fillcolor=lightgreen shape=box label="Buffering\n(arch-adaptive)"]
node [shape=record];
appthr [label="<tmain>Main\nthread|<t1>T1|<t2>T2|<tN>TN"];
cbs [style=filled fillcolor=orange shape=box label="Registered callbacks"];
cbs -> appthr [dir=both color=darkgreen]
sigtable -> cbs [color=green]
fdtable -> cbs [color=green]
twheel -> cbs [color=green]
buf -> cbs [color=green]
dnsssl -> cbs [color=green]
cbs -> API;
appthr -> API;
/*API -> fdtable [color=blueviolet]
API -> sigtable [color=blueviolet]
API -> twheel [color=blueviolet]*/
}
}
} </pre>
==PNG==
Generated with <tt>dot -Tpng</tt>, no postprocessing.
===Multiple records===
[[Image:CUDASHA1input.png|thumb|right|alt="DOT PNG example (multiple records)"|Multiple records (click to enlarge)]]
<pre>digraph G {
nodesep="0.1"
rankdir=RL;
subgraph clusterPrime {
label="SHA-1 input layout\ (b\ hashes\ per\ thread)\nNx1x1 block geometry,\ Gx1x1\ grid\ geometry";
labelloc="b";
compound="true"
subgraph clusterKernel {
color=darkgoldenrod;
style=filled;
label="bl0";
b0 [style=filled,width=5,shape=record,label="{ {Hash\ set\ 1\n(512n\ bits)}\
|{T0[0x0]|T0[0x1]|T0[...]|T0[0xf]}|{T1[0x0]|T1[0x1]|T1[...]|T1[0xf]}|{...|...|...|...}|{Tn[0x0]|Tn[0x1]|Tn[...]|Tn[0xf]}}"];
b1 [style=filled,width=5,shape=record,label="{ {Hash\ set\ b\n(512n\ bits)}\
|{T0[0x0]|T0[0x1]|T0[...]|T0[0xf]}|{T1[0x0]|T1[0x1]|T1[...]|T1[0xf]}|{...|...|...|...}|{Tn[0x0]|Tn[0x1]|Tn[...]|Tn[0xf]}}"];
label="Input to block 1 (512*n*b bits)";
}
subgraph clusterUser {
color=darkkhaki;
style=filled;
label="bl0";
b2 [style=filled,width=5,shape=record,label="{ {Hash\ set\ 1\n(512n\ bits)}\
|{T0[0x0]|T0[0x1]|T0[...]|T0[0xf]}|{T1[0x0]|T1[0x1]|T1[...]|T1[0xf]}|{...|...|...|...}|{Tn[0x0]|Tn[0x1]|Tn[...]|Tn[0xf]}}"];
b3 [style=filled,width=5,shape=record,label="{ {Hash\ set\ b\n(512n\ bits)}\
|{T0[0x0]|T0[0x1]|T0[...]|T0[0xf]}|{T1[0x0]|T1[0x1]|T1[...]|T1[0xf]}|{...|...|...|...}|{Tn[0x0]|Tn[0x1]|Tn[...]|Tn[0xf]}}"];
label="Input to block G (512*n*b bits)";
}
}
} </pre>

Dot

2012-05-13T22:19:03Z

Dank: /* Multiple records */

==SVG==
* graphviz tools generate svg via -Tsvg
* [http://github.com/vidarh/diagram-tools notugly] is some XSL to beautify dot's SVG output
==Examples==
Generated using Graphviz 2.20.2 and postprocessing via <tt>xsltproc</tt> and [http://github.com/vidarh/diagram-tools notugly]. I hand-wrote the dot sources.
===Packed Record===
[[Image:Opteron.svg|thumb|right|alt="Dot SVG example (packed record)"|A packed record-type node (click to enlarge)]]
<pre>digraph G {
subgraph clusterOpteron {
label="Quad-Core Opteron"
node [shape=record];
struct3 [label="{ {C0|C1|C2|C3}|{L1/L2|L1/L2|L1/L2|L1/L2}|SRI\
(SysReq Interface)|<xbar>XBAR (Crossbar Switch)|{MCH|ncHT-HB|HT0|HT1}}"];
}
} </pre>

===Rectilinear arrangement A===
[[Image:Deneb.svg|thumb|right|alt="Dot SVG example (rectilinear)"|A rectilinear graph (click to enlarge)]]
<pre>digraph G {
subgraph clusterOpteronNUMA {
label = "2x 'Deneb' Phenom II X4 910 (45nm, AM3). 8 threads."
Deneb0->Deneb1 [dir="both" label="2GHz 16-bit bidir\n8GB/s HyperTransport 3.0" color="blue"]
DDR0 -> Deneb0 [dir="both" color="lightblue"]
DDR1 -> Deneb1 [dir="both" color="lightblue"]
HostBus -> Deneb0 [dir="both" color="darkgreen"]
HostBus -> Deneb1 [dir="both" color="darkgreen"]
{ rank=same; Deneb0 Deneb1 }
{ rank=same; DDR0 DDR1 }
Deneb0 [style=filled fillcolor=steelblue shape=box]
Deneb1 [style=filled fillcolor=steelblue shape=box]
DDR0 [style=filled fillcolor=grey shape=invhouse]
DDR1 [style=filled fillcolor=grey shape=invhouse]
HostBus [style=filled fillcolor=green shape=Msquare]
}
}</pre>

===Rectilinear arrangement B===
[[Image:Nehalem.svg|thumb|right|alt="Dot SVG example (rectilinear)"|A rectilinear graph (click to enlarge)]]
<pre>digraph G {
nodesep="1"
subgraph clusterNehalemSMP {
DDR0 -> Nehalem0 [dir="both" color="lightblue"]
DDR0 -> Nehalem1 [dir="both" color="lightblue"]
Nehalem0->Nehalem1 [dir="both" label="25.6GB/s QuickPath" color="blue"]
subgraph clusterNehalemSMP0 {
label="DRAM may or may not be shared.";
style=filled;
color=lightgrey;
{ rank=same; DDR0 }
{ rank=same; Nehalem0 Nehalem1 }
}
Nehalem2->Nehalem3 [dir="both" label="25.6GB/s QuickPath" color="blue"]
Nehalem2 -> DDR1 [dir="both" color="lightblue"]
Nehalem3 -> DDR1 [dir="both" color="lightblue"]
subgraph clusterNehalemSMP1 {
labelloc="b";
label="Each package gets its own MCH and L3 cache,\neach core its own (split) L1 and (unified) L2.";
style=filled;
color=lightgrey;
{ rank=same; Nehalem2 Nehalem3 }
{ rank=same; DDR1 }
}
label = "4x 'Nehalem-EP' E5520 HT Core i7 (45nm LGA1336). 32 threads."
Nehalem1->Nehalem2 [dir="both" color="blue"]
Nehalem3->Nehalem0 [dir="both" color="blue"]
Nehalem0->HostBus [dir="both" color="darkgreen"]
Nehalem1->HostBus [dir="both" color="darkgreen"]
HostBus->Nehalem2 [dir="both" color="darkgreen"]
HostBus->Nehalem3 [dir="both" color="darkgreen"]
Nehalem0 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
Nehalem1 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
Nehalem2 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
Nehalem3 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
DDR0 [style=filled fillcolor=grey shape=invtrapezium]
DDR1 [style=filled fillcolor=grey shape=trapezium]
HostBus [style=filled fillcolor=green shape=Msquare]
}
} </pre>
===Large flow===
[[Image:libtorque.svg|thumb|right|alt="DOT SVG example (large flow)"|A large flow (click to enlarge)]]
<pre>digraph G {
nodesep="0.5"
subgraph clusterPrime {
labelloc="b";
compound="true"
subgraph clusterKernel {
label="Kernelspace (Linux epoll, FreeBSD kqueue, etc...)"
style=filled;
color=cadetblue;
wqueue0 [style=filled fillcolor=steelblue shape=Mdiamond]
wqueueN [style=filled fillcolor=steelblue shape=Mdiamond]
wqueue0 -> nics [dir=both]
nics [style="filled,diagonals" fillcolor=greenyellow label="Devices/IPC"]
nics -> wqueueN [dir=both]
{ rank=same; wqueue0 wqueueN nics }
}
subgraph clusterUser {
label="Userspace (libtorque-enabled process)";
style=filled;
color=gold;
evqueueN [style="diagonals,filled" fillcolor=mediumpurple shape=invtrapezium group="evq"]
evqueue0 [style="diagonals,filled" fillcolor=mediumpurple shape=invtrapezium group="evq"]
wqueue0 -> evqueue0 [dir=both style=bold color="blue:purple"]
wqueueN -> evqueueN [dir=both style=bold color="blue:purple"]
evqueue0 -> evqueueN [label="About sqrt(cpus) evqueues, usually" dir=both style=dotted color=maroon]
API -> evqueue0 [style=bold color=purple]
API -> evqueueN [style=bold color=purple]
API [style=filled fillcolor=green shape=box group="evq"];
{ rank=same; evqueue0 evqueueN }
node [shape=record];
thr0 [label="<t0>T0|<t1>T1|<t2>T2|<tN>TN"];
thrN [label="<t0>T0|<t1>T1|<t2>T2|<tN>TN"];
color=red;
evqueue0 -> thr0:t0 [color=blue]
evqueue0 -> thr0:t1 [color=blue]
evqueue0 -> thr0:t2 [color=blue]
evqueue0 -> thr0:tN [color=blue]
evqueueN -> thrN:t0 [color=blue]
evqueueN -> thrN:t1 [color=blue]
evqueueN -> thrN:t2 [color=blue]
evqueueN -> thrN:tN [color=blue]
{ rank=same; thr0 thrN }
thr0 -> sigtable [color=lightblue style=bold]
thr0 -> fdtable [color=lightblue style=bold]
thr0 -> twheel [color=lightblue style=bold]
thrN -> sigtable [color=lightblue style=bold]
thrN -> fdtable [color=lightblue style=bold]
thrN -> twheel [color=lightblue style=bold]
fdtable [style=filled fillcolor=lightgreen shape=box label="fd monads\n(array)"]
twheel [style=filled fillcolor=lightgreen shape=box label="timer monads\n(hwheel or array)"]
sigtable [style=filled fillcolor=lightgreen shape=box label="sig monads\n(array)"]
sigtable -> fdtable [color=lightblue label="AIO"]
fdtable -> buf [color=lightblue]
fdtable -> dnsssl [color=lightblue]
twheel -> dnsssl [color=lightblue]
buf -> API
{ rank=same; sigtable fdtable twheel }
dnsssl -> API
dnsssl [style=filled fillcolor=lightgreen shape=box label="DNS, SSL/TLS\n(adns, OpenSSL)"]
buf [style=filled fillcolor=lightgreen shape=box label="Buffering\n(arch-adaptive)"]
node [shape=record];
appthr [label="<tmain>Main\nthread|<t1>T1|<t2>T2|<tN>TN"];
cbs [style=filled fillcolor=orange shape=box label="Registered callbacks"];
cbs -> appthr [dir=both color=darkgreen]
sigtable -> cbs [color=green]
fdtable -> cbs [color=green]
twheel -> cbs [color=green]
buf -> cbs [color=green]
dnsssl -> cbs [color=green]
cbs -> API;
appthr -> API;
/*API -> fdtable [color=blueviolet]
API -> sigtable [color=blueviolet]
API -> twheel [color=blueviolet]*/
}
}
} </pre>
==PNG==
===Multiple records===
[[Image:CUDASHA1input.png|thumb|right|alt="DOT PNG example (multiple records)"|Multiple records (click to enlarge)]]
<pre>digraph G {
nodesep="0.1"
rankdir=RL;
subgraph clusterPrime {
label="SHA-1 input layout\ (b\ hashes\ per\ thread)\nNx1x1 block geometry,\ Gx1x1\ grid\ geometry";
labelloc="b";
compound="true"
subgraph clusterKernel {
color=darkgoldenrod;
style=filled;
label="bl0";
b0 [style=filled,width=5,shape=record,label="{ {Hash\ set\ 1\n(512n\ bits)}\
|{T0[0x0]|T0[0x1]|T0[...]|T0[0xf]}|{T1[0x0]|T1[0x1]|T1[...]|T1[0xf]}|{...|...|...|...}|{Tn[0x0]|Tn[0x1]|Tn[...]|Tn[0xf]}}"];
b1 [style=filled,width=5,shape=record,label="{ {Hash\ set\ b\n(512n\ bits)}\
|{T0[0x0]|T0[0x1]|T0[...]|T0[0xf]}|{T1[0x0]|T1[0x1]|T1[...]|T1[0xf]}|{...|...|...|...}|{Tn[0x0]|Tn[0x1]|Tn[...]|Tn[0xf]}}"];
label="Input to block 1 (512*n*b bits)";
}
subgraph clusterUser {
color=darkkhaki;
style=filled;
label="bl0";
b2 [style=filled,width=5,shape=record,label="{ {Hash\ set\ 1\n(512n\ bits)}\
|{T0[0x0]|T0[0x1]|T0[...]|T0[0xf]}|{T1[0x0]|T1[0x1]|T1[...]|T1[0xf]}|{...|...|...|...}|{Tn[0x0]|Tn[0x1]|Tn[...]|Tn[0xf]}}"];
b3 [style=filled,width=5,shape=record,label="{ {Hash\ set\ b\n(512n\ bits)}\
|{T0[0x0]|T0[0x1]|T0[...]|T0[0xf]}|{T1[0x0]|T1[0x1]|T1[...]|T1[0xf]}|{...|...|...|...}|{Tn[0x0]|Tn[0x1]|Tn[...]|Tn[0xf]}}"];
label="Input to block G (512*n*b bits)";
}
}
} </pre>

Dot

2012-05-13T22:18:23Z

Dank: /* PNG */

==SVG==
* graphviz tools generate svg via -Tsvg
* [http://github.com/vidarh/diagram-tools notugly] is some XSL to beautify dot's SVG output
==Examples==
Generated using Graphviz 2.20.2 and postprocessing via <tt>xsltproc</tt> and [http://github.com/vidarh/diagram-tools notugly]. I hand-wrote the dot sources.
===Packed Record===
[[Image:Opteron.svg|thumb|right|alt="Dot SVG example (packed record)"|A packed record-type node (click to enlarge)]]
<pre>digraph G {
subgraph clusterOpteron {
label="Quad-Core Opteron"
node [shape=record];
struct3 [label="{ {C0|C1|C2|C3}|{L1/L2|L1/L2|L1/L2|L1/L2}|SRI\
(SysReq Interface)|<xbar>XBAR (Crossbar Switch)|{MCH|ncHT-HB|HT0|HT1}}"];
}
} </pre>

===Rectilinear arrangement A===
[[Image:Deneb.svg|thumb|right|alt="Dot SVG example (rectilinear)"|A rectilinear graph (click to enlarge)]]
<pre>digraph G {
subgraph clusterOpteronNUMA {
label = "2x 'Deneb' Phenom II X4 910 (45nm, AM3). 8 threads."
Deneb0->Deneb1 [dir="both" label="2GHz 16-bit bidir\n8GB/s HyperTransport 3.0" color="blue"]
DDR0 -> Deneb0 [dir="both" color="lightblue"]
DDR1 -> Deneb1 [dir="both" color="lightblue"]
HostBus -> Deneb0 [dir="both" color="darkgreen"]
HostBus -> Deneb1 [dir="both" color="darkgreen"]
{ rank=same; Deneb0 Deneb1 }
{ rank=same; DDR0 DDR1 }
Deneb0 [style=filled fillcolor=steelblue shape=box]
Deneb1 [style=filled fillcolor=steelblue shape=box]
DDR0 [style=filled fillcolor=grey shape=invhouse]
DDR1 [style=filled fillcolor=grey shape=invhouse]
HostBus [style=filled fillcolor=green shape=Msquare]
}
}</pre>

===Rectilinear arrangement B===
[[Image:Nehalem.svg|thumb|right|alt="Dot SVG example (rectilinear)"|A rectilinear graph (click to enlarge)]]
<pre>digraph G {
nodesep="1"
subgraph clusterNehalemSMP {
DDR0 -> Nehalem0 [dir="both" color="lightblue"]
DDR0 -> Nehalem1 [dir="both" color="lightblue"]
Nehalem0->Nehalem1 [dir="both" label="25.6GB/s QuickPath" color="blue"]
subgraph clusterNehalemSMP0 {
label="DRAM may or may not be shared.";
style=filled;
color=lightgrey;
{ rank=same; DDR0 }
{ rank=same; Nehalem0 Nehalem1 }
}
Nehalem2->Nehalem3 [dir="both" label="25.6GB/s QuickPath" color="blue"]
Nehalem2 -> DDR1 [dir="both" color="lightblue"]
Nehalem3 -> DDR1 [dir="both" color="lightblue"]
subgraph clusterNehalemSMP1 {
labelloc="b";
label="Each package gets its own MCH and L3 cache,\neach core its own (split) L1 and (unified) L2.";
style=filled;
color=lightgrey;
{ rank=same; Nehalem2 Nehalem3 }
{ rank=same; DDR1 }
}
label = "4x 'Nehalem-EP' E5520 HT Core i7 (45nm LGA1336). 32 threads."
Nehalem1->Nehalem2 [dir="both" color="blue"]
Nehalem3->Nehalem0 [dir="both" color="blue"]
Nehalem0->HostBus [dir="both" color="darkgreen"]
Nehalem1->HostBus [dir="both" color="darkgreen"]
HostBus->Nehalem2 [dir="both" color="darkgreen"]
HostBus->Nehalem3 [dir="both" color="darkgreen"]
Nehalem0 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
Nehalem1 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
Nehalem2 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
Nehalem3 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
DDR0 [style=filled fillcolor=grey shape=invtrapezium]
DDR1 [style=filled fillcolor=grey shape=trapezium]
HostBus [style=filled fillcolor=green shape=Msquare]
}
} </pre>
===Large flow===
[[Image:libtorque.svg|thumb|right|alt="DOT SVG example (large flow)"|A large flow (click to enlarge)]]
<pre>digraph G {
nodesep="0.5"
subgraph clusterPrime {
labelloc="b";
compound="true"
subgraph clusterKernel {
label="Kernelspace (Linux epoll, FreeBSD kqueue, etc...)"
style=filled;
color=cadetblue;
wqueue0 [style=filled fillcolor=steelblue shape=Mdiamond]
wqueueN [style=filled fillcolor=steelblue shape=Mdiamond]
wqueue0 -> nics [dir=both]
nics [style="filled,diagonals" fillcolor=greenyellow label="Devices/IPC"]
nics -> wqueueN [dir=both]
{ rank=same; wqueue0 wqueueN nics }
}
subgraph clusterUser {
label="Userspace (libtorque-enabled process)";
style=filled;
color=gold;
evqueueN [style="diagonals,filled" fillcolor=mediumpurple shape=invtrapezium group="evq"]
evqueue0 [style="diagonals,filled" fillcolor=mediumpurple shape=invtrapezium group="evq"]
wqueue0 -> evqueue0 [dir=both style=bold color="blue:purple"]
wqueueN -> evqueueN [dir=both style=bold color="blue:purple"]
evqueue0 -> evqueueN [label="About sqrt(cpus) evqueues, usually" dir=both style=dotted color=maroon]
API -> evqueue0 [style=bold color=purple]
API -> evqueueN [style=bold color=purple]
API [style=filled fillcolor=green shape=box group="evq"];
{ rank=same; evqueue0 evqueueN }
node [shape=record];
thr0 [label="<t0>T0|<t1>T1|<t2>T2|<tN>TN"];
thrN [label="<t0>T0|<t1>T1|<t2>T2|<tN>TN"];
color=red;
evqueue0 -> thr0:t0 [color=blue]
evqueue0 -> thr0:t1 [color=blue]
evqueue0 -> thr0:t2 [color=blue]
evqueue0 -> thr0:tN [color=blue]
evqueueN -> thrN:t0 [color=blue]
evqueueN -> thrN:t1 [color=blue]
evqueueN -> thrN:t2 [color=blue]
evqueueN -> thrN:tN [color=blue]
{ rank=same; thr0 thrN }
thr0 -> sigtable [color=lightblue style=bold]
thr0 -> fdtable [color=lightblue style=bold]
thr0 -> twheel [color=lightblue style=bold]
thrN -> sigtable [color=lightblue style=bold]
thrN -> fdtable [color=lightblue style=bold]
thrN -> twheel [color=lightblue style=bold]
fdtable [style=filled fillcolor=lightgreen shape=box label="fd monads\n(array)"]
twheel [style=filled fillcolor=lightgreen shape=box label="timer monads\n(hwheel or array)"]
sigtable [style=filled fillcolor=lightgreen shape=box label="sig monads\n(array)"]
sigtable -> fdtable [color=lightblue label="AIO"]
fdtable -> buf [color=lightblue]
fdtable -> dnsssl [color=lightblue]
twheel -> dnsssl [color=lightblue]
buf -> API
{ rank=same; sigtable fdtable twheel }
dnsssl -> API
dnsssl [style=filled fillcolor=lightgreen shape=box label="DNS, SSL/TLS\n(adns, OpenSSL)"]
buf [style=filled fillcolor=lightgreen shape=box label="Buffering\n(arch-adaptive)"]
node [shape=record];
appthr [label="<tmain>Main\nthread|<t1>T1|<t2>T2|<tN>TN"];
cbs [style=filled fillcolor=orange shape=box label="Registered callbacks"];
cbs -> appthr [dir=both color=darkgreen]
sigtable -> cbs [color=green]
fdtable -> cbs [color=green]
twheel -> cbs [color=green]
buf -> cbs [color=green]
dnsssl -> cbs [color=green]
cbs -> API;
appthr -> API;
/*API -> fdtable [color=blueviolet]
API -> sigtable [color=blueviolet]
API -> twheel [color=blueviolet]*/
}
}
} </pre>
==PNG==
===Multiple records===
[[Image:CUDASHA1input.png|thumb|right|alt="DOT PNG example (multiple records)"|Multiple records (click to enlarge)]]
<pre>digraph G {
nodesep="0.1"
rankdir=RL;
subgraph clusterPrime {
label="SHA-1 input layout\ (b\ hashes\ per\ thread)\nNx1x1 block geometry,\ Gx1x1\ grid\ geometry";
labelloc="b";
compound="true"
subgraph clusterKernel {
color=darkgoldenrod;
style=filled;
label="bl0";
b0 [style=filled,width=5,shape=record,label="{ {Hash\ set\ 1\n(512n\ bits)}|{T0[0x0]|T0[0x1]|T0[...]|T0[0xf]}|{T1[0x0]|T1[0x1]|T1[...]|T1[0xf]}|{...|...|...|...}|{Tn[0x0]|Tn[0x1]|Tn[...]|Tn[0xf]}}"];
b1 [style=filled,width=5,shape=record,label="{ {Hash\ set\ b\n(512n\ bits)}|{T0[0x0]|T0[0x1]|T0[...]|T0[0xf]}|{T1[0x0]|T1[0x1]|T1[...]|T1[0xf]}|{...|...|...|...}|{Tn[0x0]|Tn[0x1]|Tn[...]|Tn[0xf]}}"];
label="Input to block 1 (512*n*b bits)";
}
subgraph clusterUser {
color=darkkhaki;
style=filled;
label="bl0";
b2 [style=filled,width=5,shape=record,label="{ {Hash\ set\ 1\n(512n\ bits)}|{T0[0x0]|T0[0x1]|T0[...]|T0[0xf]}|{T1[0x0]|T1[0x1]|T1[...]|T1[0xf]}|{...|...|...|...}|{Tn[0x0]|Tn[0x1]|Tn[...]|Tn[0xf]}}"];
b3 [style=filled,width=5,shape=record,label="{ {Hash\ set\ b\n(512n\ bits)}|{T0[0x0]|T0[0x1]|T0[...]|T0[0xf]}|{T1[0x0]|T1[0x1]|T1[...]|T1[0xf]}|{...|...|...|...}|{Tn[0x0]|Tn[0x1]|Tn[...]|Tn[0xf]}}"];
label="Input to block G (512*n*b bits)";
}
}
} </pre>

Dot

2012-05-13T22:17:55Z

Dank:

==SVG==
* graphviz tools generate svg via -Tsvg
* [http://github.com/vidarh/diagram-tools notugly] is some XSL to beautify dot's SVG output
==Examples==
Generated using Graphviz 2.20.2 and postprocessing via <tt>xsltproc</tt> and [http://github.com/vidarh/diagram-tools notugly]. I hand-wrote the dot sources.
===Packed Record===
[[Image:Opteron.svg|thumb|right|alt="Dot SVG example (packed record)"|A packed record-type node (click to enlarge)]]
<pre>digraph G {
subgraph clusterOpteron {
label="Quad-Core Opteron"
node [shape=record];
struct3 [label="{ {C0|C1|C2|C3}|{L1/L2|L1/L2|L1/L2|L1/L2}|SRI\
(SysReq Interface)|<xbar>XBAR (Crossbar Switch)|{MCH|ncHT-HB|HT0|HT1}}"];
}
} </pre>

===Rectilinear arrangement A===
[[Image:Deneb.svg|thumb|right|alt="Dot SVG example (rectilinear)"|A rectilinear graph (click to enlarge)]]
<pre>digraph G {
subgraph clusterOpteronNUMA {
label = "2x 'Deneb' Phenom II X4 910 (45nm, AM3). 8 threads."
Deneb0->Deneb1 [dir="both" label="2GHz 16-bit bidir\n8GB/s HyperTransport 3.0" color="blue"]
DDR0 -> Deneb0 [dir="both" color="lightblue"]
DDR1 -> Deneb1 [dir="both" color="lightblue"]
HostBus -> Deneb0 [dir="both" color="darkgreen"]
HostBus -> Deneb1 [dir="both" color="darkgreen"]
{ rank=same; Deneb0 Deneb1 }
{ rank=same; DDR0 DDR1 }
Deneb0 [style=filled fillcolor=steelblue shape=box]
Deneb1 [style=filled fillcolor=steelblue shape=box]
DDR0 [style=filled fillcolor=grey shape=invhouse]
DDR1 [style=filled fillcolor=grey shape=invhouse]
HostBus [style=filled fillcolor=green shape=Msquare]
}
}</pre>

===Rectilinear arrangement B===
[[Image:Nehalem.svg|thumb|right|alt="Dot SVG example (rectilinear)"|A rectilinear graph (click to enlarge)]]
<pre>digraph G {
nodesep="1"
subgraph clusterNehalemSMP {
DDR0 -> Nehalem0 [dir="both" color="lightblue"]
DDR0 -> Nehalem1 [dir="both" color="lightblue"]
Nehalem0->Nehalem1 [dir="both" label="25.6GB/s QuickPath" color="blue"]
subgraph clusterNehalemSMP0 {
label="DRAM may or may not be shared.";
style=filled;
color=lightgrey;
{ rank=same; DDR0 }
{ rank=same; Nehalem0 Nehalem1 }
}
Nehalem2->Nehalem3 [dir="both" label="25.6GB/s QuickPath" color="blue"]
Nehalem2 -> DDR1 [dir="both" color="lightblue"]
Nehalem3 -> DDR1 [dir="both" color="lightblue"]
subgraph clusterNehalemSMP1 {
labelloc="b";
label="Each package gets its own MCH and L3 cache,\neach core its own (split) L1 and (unified) L2.";
style=filled;
color=lightgrey;
{ rank=same; Nehalem2 Nehalem3 }
{ rank=same; DDR1 }
}
label = "4x 'Nehalem-EP' E5520 HT Core i7 (45nm LGA1336). 32 threads."
Nehalem1->Nehalem2 [dir="both" color="blue"]
Nehalem3->Nehalem0 [dir="both" color="blue"]
Nehalem0->HostBus [dir="both" color="darkgreen"]
Nehalem1->HostBus [dir="both" color="darkgreen"]
HostBus->Nehalem2 [dir="both" color="darkgreen"]
HostBus->Nehalem3 [dir="both" color="darkgreen"]
Nehalem0 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
Nehalem1 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
Nehalem2 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
Nehalem3 [style=filled fillcolor=steelblue shape=box label="4x 2-way cores"]
DDR0 [style=filled fillcolor=grey shape=invtrapezium]
DDR1 [style=filled fillcolor=grey shape=trapezium]
HostBus [style=filled fillcolor=green shape=Msquare]
}
} </pre>
===Large flow===
[[Image:libtorque.svg|thumb|right|alt="DOT SVG example (large flow)"|A large flow (click to enlarge)]]
<pre>digraph G {
nodesep="0.5"
subgraph clusterPrime {
labelloc="b";
compound="true"
subgraph clusterKernel {
label="Kernelspace (Linux epoll, FreeBSD kqueue, etc...)"
style=filled;
color=cadetblue;
wqueue0 [style=filled fillcolor=steelblue shape=Mdiamond]
wqueueN [style=filled fillcolor=steelblue shape=Mdiamond]
wqueue0 -> nics [dir=both]
nics [style="filled,diagonals" fillcolor=greenyellow label="Devices/IPC"]
nics -> wqueueN [dir=both]
{ rank=same; wqueue0 wqueueN nics }
}
subgraph clusterUser {
label="Userspace (libtorque-enabled process)";
style=filled;
color=gold;
evqueueN [style="diagonals,filled" fillcolor=mediumpurple shape=invtrapezium group="evq"]
evqueue0 [style="diagonals,filled" fillcolor=mediumpurple shape=invtrapezium group="evq"]
wqueue0 -> evqueue0 [dir=both style=bold color="blue:purple"]
wqueueN -> evqueueN [dir=both style=bold color="blue:purple"]
evqueue0 -> evqueueN [label="About sqrt(cpus) evqueues, usually" dir=both style=dotted color=maroon]
API -> evqueue0 [style=bold color=purple]
API -> evqueueN [style=bold color=purple]
API [style=filled fillcolor=green shape=box group="evq"];
{ rank=same; evqueue0 evqueueN }
node [shape=record];
thr0 [label="<t0>T0|<t1>T1|<t2>T2|<tN>TN"];
thrN [label="<t0>T0|<t1>T1|<t2>T2|<tN>TN"];
color=red;
evqueue0 -> thr0:t0 [color=blue]
evqueue0 -> thr0:t1 [color=blue]
evqueue0 -> thr0:t2 [color=blue]
evqueue0 -> thr0:tN [color=blue]
evqueueN -> thrN:t0 [color=blue]
evqueueN -> thrN:t1 [color=blue]
evqueueN -> thrN:t2 [color=blue]
evqueueN -> thrN:tN [color=blue]
{ rank=same; thr0 thrN }
thr0 -> sigtable [color=lightblue style=bold]
thr0 -> fdtable [color=lightblue style=bold]
thr0 -> twheel [color=lightblue style=bold]
thrN -> sigtable [color=lightblue style=bold]
thrN -> fdtable [color=lightblue style=bold]
thrN -> twheel [color=lightblue style=bold]
fdtable [style=filled fillcolor=lightgreen shape=box label="fd monads\n(array)"]
twheel [style=filled fillcolor=lightgreen shape=box label="timer monads\n(hwheel or array)"]
sigtable [style=filled fillcolor=lightgreen shape=box label="sig monads\n(array)"]
sigtable -> fdtable [color=lightblue label="AIO"]
fdtable -> buf [color=lightblue]
fdtable -> dnsssl [color=lightblue]
twheel -> dnsssl [color=lightblue]
buf -> API
{ rank=same; sigtable fdtable twheel }
dnsssl -> API
dnsssl [style=filled fillcolor=lightgreen shape=box label="DNS, SSL/TLS\n(adns, OpenSSL)"]
buf [style=filled fillcolor=lightgreen shape=box label="Buffering\n(arch-adaptive)"]
node [shape=record];
appthr [label="<tmain>Main\nthread|<t1>T1|<t2>T2|<tN>TN"];
cbs [style=filled fillcolor=orange shape=box label="Registered callbacks"];
cbs -> appthr [dir=both color=darkgreen]
sigtable -> cbs [color=green]
fdtable -> cbs [color=green]
twheel -> cbs [color=green]
buf -> cbs [color=green]
dnsssl -> cbs [color=green]
cbs -> API;
appthr -> API;
/*API -> fdtable [color=blueviolet]
API -> sigtable [color=blueviolet]
API -> twheel [color=blueviolet]*/
}
}
} </pre>
==PNG==
===Multiple records===
[[Image:CUDASHA1input.png|thumb|right|alt="DOT PNG example (multiple records)"|Multiple records (click to enlarge)]]

File:CUDASHA1input.png

2012-05-13T22:16:39Z

Dank: Optimal data input layout for CUDA SHA-1

Optimal data input layout for CUDA SHA-1

Compiler Design

2012-05-12T20:22:56Z

Dank: /* See Also */ fix syntax

==Control Flow Analysis==
Subsequent branch-free instructions make up segments of ''linear code''. The first instruction of the program is a ''leader'', as is every target of a branch, and every instruction immediately following a branch (including conditional branches and procedure returns) is a leader. A ''basic block'' is the maximum segment of linear code associated with each leader -- it ends with either the program's last instruction or the first branch following a leader. ''Points'' exist before and after each statement in a basic block (there are thus a minimum of 2 points per block, and s + 1 for a block with s statements). A basic block a ''flows'' to b if and only if:
* either b immediately follows a, and a does not end in an unconditional branch,
* or a ends in a branch, of which b is a potential target.
Note that an indirect branch, without context information, trivializes all blocks (every instruction becomes a leader) and flows to them all from at least that point (an arborescence is induced)!

The directed multigraph defined by interpreting basic blocks as vertices, and flow relationships as edges, yields its control flow graph (CFG). A start node exists for each CFG, corresponding to the basic block whose header is the first instruction of the program.

The antisymmetric, transitive, reflexive ''domination relation'' is defined on vertices of a CFG (and thus basic blocks of the underlying program). A vertex a ''dominates'' b (a <= b) if every path from the start node s to b passes through a. A vertex a ''properly dominates'' b (a < b) if a dominates and is not equal to b. A vertex a ''directly/immediately dominates'' b (a <d b) if a properly dominates b, and a dominates no vertex c that dominates b. This relation induces the [[Trees|dominator tree]], where nodes dominate all descendents in the tree. The start node s dominates all nodes, properly dominates all nodes but itself, and roots the dominator tree.
* It should be obvious that a's preceding of b in the CFG is not necessary for even immediate dominance of b by a.
''Paths'' p1,p2...pn are defined as sequences of points such that either pi+1 immediately follows pi in a basic block, or pi+1 begins a successor block to a block terminated by pi. It is on these points that dataflow equations are evaluated.

Dataflow analysis is most usefully performed into and out of ''regions'', subsets of the nodes such that a ''header'' exists which dominates all nodes in the region, and all edges between nodes in the region are themselves in the region. A loop is a region which is strongly connected, where all back-edges to the header are themselves within the region '''FIXME -- unclear'''.

Loops can be discovered via domination analysis (it is important to note that this refers to loops in the generated code, not loop constructs of the source language, and furthermore that all possible loops will be found (ie, unstructured loops constructed from C <tt>gotos</tt>)). Discover all strongly-connected subgraphs (SCCs) of the CFG (subgraphs where, for each vertex, a path ('''not''' necessarily an edge) exists from that vertex to all other nodes of the subgraph); if a subgraph contains a node dominating all that subgraph's nodes, the subgraph is a loop. The trivial case is, of course, a statement which jumps to itself, ala the BASIC program <tt>10 GOTO 10</tt>. Implementation via [[Kosaraju's Algorithm]] is simple, with O(|V|+|E|) time complexity using graph encoding and O(N2) time complexity using adjacency matrices:
* Perform a recursive depth-first traversal of the graph starting from s. Each time you return, add that node onto an auxiliary vector. Upon the traversal's completion, this vector sorts the nodes topologically.
* Until the the vector is empty, use the last node of the vector to begin traversing the transpose graph. Remove the path from the vector; these paths partition the graph into SCCs.
Kosaraju's algorithm is improved upon by [[Tarjan's Algorithm]] and [[Gabow's Algorithm]].
''Natural loop'' identification proceeds via identification of ''back edges'' (edges from a node b to a node a, where a dominates b). A loop is associated with every such back edge; if a backedge exists from b to a, the associated loop is entered at a, and consists additionally of all nodes which can reach b without going through a. Similarly, a loop is associated with the target of every back edge, this being the union of all such backedges' associated natural loops.

===Dead code elimination===
Control flow analysis by itself is sufficient to remove some ''unreachable code'' (viz ''dead code'', below).

==Dataflow/Dependency Analysis==
One major purpose of dataflow analysis is observing safety constraints across reordering transformations.
If a statement S writes to a variable V, S is said to ''define'' V. If statement S reads from a variable V, S is said to ''use'' V (the two are not mutually exclusive). A definition of v is ''killed'' between p1 and p2 if every path between them contains a definition of v; conversely, if a path exists from p1 to p2 which does not redefine v, and v has been defined on input to p1, it ''reaches'' p2 from p1. In this situation, v would furthermore be ''live'' at p1 (or immediately after p1, if p1 assigned it); a variable is live at a point if that instantiation of the variable might be used in the future.
* Reaching analysis -- forwards dataflow problem, set union as confluence operator
** Copy propagation eliminates assignment statements, when safe (when modification of upwards-exposed uses of the target may be modified)
* Liveness analysis -- backwards-may dataflow problem, set union as confluence operator
** Use-Define chain -- a use U of a variable, and all definitions of that variable which can reach it (those live relative to U)
** Def-Use chain -- a definition D of a variable, and all uses of that variable it can reach (those reached from D)
** Common subexpression elimination lexically matches subexpressions, and can preserve them in registers
** Liveness analysis can detect some instances of ''dead code'' (code whose result is never used, viz ''unreachable code'' above)

===Intermediate Representations===
* Code is in ''Three-operand'' form iff instructions have no more than 1 destination and no more than 2 sources
* Three-operand code is in ''Single Static Assignment'' form iff for each variable, that variable is defined at most once, and that definition dominates every use of said variable.
** This requires the introduction of Φ-nodes, unions of possible values used in definitions ('''FIXME''' describe dominance frontiers etc, develop all of this)
* SSA and CPS (Continuation-Passing Style) are equivalent (Kelsey 1995, Appel 1998 '''FIXME full citations!''')
* SSA makes use-def chains explicit, and restricts them to a single element each
* It's much easier to perform global value numbering optimizations in this representation (see Muchnick, p378-396)
** Global value numbering is much more complete that basic common subexpression elimination
** Partial redundancy elimination can be unified with global value numbering
** Lazy code motion is described in Muchnick p. 407-415

===Loops===
* Primary references: Allen/Kennedy ch. 2-3, Muchnick ch. 14
* Statement order within a loop is never a factor in preserving loop-carried dependencies

===Pointers/Aliasing===
* Why people still write in FORTRAN instead of C
* Type-based analysis (see [[C99|ANSI C99's]] <tt>restrict</tt> keyword), [[gcc]]'s <tt>-fstrict-aliasing</tt> directive)
** Andersen's points-to analysis is cubic but more precise than Steensgaard's essentially-linear algorithm (See [http://www.cs.wisc.edu/wpis/papers/popl97.ps "Fast and Accurate Flow-Insensitive Points-To Analysis"] (Shapiro, Horwitz, 1997))

==Memory Hierarchy==
===The role of data dependence in memory optimization===
* Allen/Kennedy p.383 sums up dataflow analysis's dual nature beautifully. '''FIXME''' rip it off
* A value computed at the dependence's source (write) and used at its sink (read) is a ''true/flow dependence''
** Once brought to a lower-level memory, it can be used without refetch so long as it's preserved
* A value read prior to being recomputed is an ''antidependence''
** Can exploit sub-unit spatial dependence, primarily with cache blocks
* A value assigned, and then reassigned prior to use, is an ''output dependence''
** Restricts life of usages (provides more precise temporal locality information)
* A value read, and then read again prior to use, is an ''input dependence''
** Groups life of usages together (provides more complete temporal locality information)

===Registers===
* Primary references: Allen/Kennedy ch. 8, Muchnick ch. 16
* Take advantage of temporal locality and, in a sense, spatial locality at the subword level.
* Loop fusion merges loops in order to enhance temporal locality
** Especially relevant for machine-generated (preprocessed) input

===Caches===
* Primary references: Allen/Kennedy ch. 9, Muchnick ch. 20. See also [[Architecture#Caches|Caches]] on the [[Architecture]] page.
* The benefits of spatial locality can now be taken advantage of at the more natural word level.
* Loop interchange -- are we striding through nested loops optimally? If not, we can interchange levels, provided all dependencies are preserved. Especially powerful when combined with hardware- or software-based prefetching and further augmented with non-blocking caches. Optimal interpositioning is NP-hard in general but excellent heuristics exist. See Allen/Kennedy p. 472-474.
** This can be valuable enough that we perform small transformations to accommodate it: loop alignment, loop peeling, etc
* Loop blocking/tiling/strip-mining -- breaking out subloops to work on a cache-friendly block at once
** Especially good for parallelizing across coherent processing elements with local, coherent caches -- coherency traffic is minimized
** Also well-suited for cases of reuse between iterations of a non-innermost loop
* Loop safety is closed under blocking operations, but not necessarily under interchange.
** Blocking can, in some cases, make subsequent interchange safe! "If the strip size is less than or equal to the threshold of the dependence that might prevent interchange, then the strip-mine-and-interchange is legal, even though the interchange would not be." (Allen/Kennedy p. 480)

==See Also==
* [[gcc]]
* [http://scienceblogs.com/goodmath/2007/10/computing_strongly_connected_c.php Computing Strongly Connected Subgraphs] from [http://scienceblogs.com/goodmath Good Math, Bad Math]
* The [http://llvm.org/ LLVM] Compiler Infrastructure Project at [http://www.cs.uiuc.edu/ UIUC]
* GCC's [http://gcc.gnu.org/projects/tree-ssa/ SSA for Trees] project page
* "[http://www.cs.lth.se/home/Jonas_Skeppstedt/kongstad.pdf An Implementation of Global Value Numbering in the GNU Compiler Collection, with Performance Measurements]" (Kongstad 2004)
* "[http://portal.acm.org/citation.cfm?id=255129.255158 On the perfect accuracy of an approximate subscript analysis test]" (Klappholz, Psarris, Kong, 1990) analyzes the GCD and [[Banerjee Inequality|Banerjee inequalities]], explaining the crappiness of the former and general robustness of the latter.
** "[http://portal.acm.org/citation.cfm?id=110518.110525&coll=&dl=ACM&CFID=15151515&CFTOKEN=6184618 On the Accuracy of the Banerjee Test]" (same authors, 1991) suggests improvements on the [[Banerjee Inequality|Banerjee test]].
* "[http://portal.acm.org/citation.cfm?id=143129&dl=GUIDE&coll=GUIDE&CFID=31575025&CFTOKEN=24090323 Eliminating False Data Dependencies using the Omega Test]" (Pugh, Wonnacott, 1992) moves from integer programming-based ([http://mathworld.wolfram.com/DiophantineEquation.html Diophantine]) solutions to a subclass of the [http://en.wikipedia.org/wiki/Presburger_arithmetic Presburger formulae].
* "[http://coyotegulch.com/products/acovea/ Acovea: Using Natural Selection to Investigate Software Complexities]" explores the gcc optimization flag space for a given chunk of code
* "[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.5532 Combining Register Allocation and Instruction Scheduling]", a seminal 1995 paper by Motwani et al, explores the complexity of scheduling

CUDA

2012-05-07T20:08:04Z

Dank: /* Compute Capabilities */ resource table

[[File:Gt200die-big.jpg|right|thumb|A "Fermi" GT200 die]]
==Hardware==
NVIDIA maintains a list of [http://www.nvidia.com/object/cuda_learn_products.html supported hardware]. For actual hardware, you'll need the "nvidia.ko" kernel module. Download the <tt>nvidia-kernel-source</tt> and <tt>nvidia-kernel-common</tt> packages, unpack <tt>/usr/src/nvidia-kernel.tar.bz2</tt>, and run <tt>make-kpkg modules_image</tt>. Install the resulting .deb, and modprobe nvidia. You'll see something like this in dmesg output:<pre>nvidia: module license 'NVIDIA' taints kernel.
Disabling lock debugging due to kernel taint
nvidia 0000:07:00.0: enabling device (0000 -> 0003)
nvidia 0000:07:00.0: PCI INT A -> GSI 21 (level, low) -> IRQ 21
nvidia 0000:07:00.0: setting latency timer to 64
NVRM: loading NVIDIA UNIX x86_64 Kernel Module 190.53 Wed Dec 9 15:29:46 PST 2009</pre>
Once the module is loaded, CUDA should be able to find the device. See [[CUDA#deviceQuery_Output|below]] for sample outputs. Each device has a '''compute capability''', though this does not encompass all differentiated capabilities (see also <tt>deviceOverlap</tt> and <tt>canMapHostMemory</tt>...). Note that "emulation mode" has been removed as of CUDA Toolkit Version 3.1.
==CUDA model==
===Host===
* A host contains zero or more CUDA-capable devices (emulation must be used if zero devices are available).
* It can run multiple CUDA processes, each composed of one or more host threads.
* A given host thread can execute code on only one device at once.
* Multiple host threads can execute code on the same device.
===Device===
* A device packages a streaming processor array (SPA), a memory interface, and possibly memory (''global memory''. ''device memory'').
** In CUDA terminology, an ''integrated'' (vs ''discrete'') device does not have its own global memory.
** Specially-prepared global memory is designated ''constant memory'', and can be [[#Streaming Multiprocessors|cached]].
* Pinned (''locked'') host memory avoids a bounce buffer, accelerating transfers.
** Larger one-time setup cost due to device register programming for DMA transfers.
** This memory will be unswappable -- allocate only as much as is needed.
* Pinned memory can be mapped directly into CUDAspace on ''integrated'' devices or in the presence of some [[IOMMU|IOMMUs]].
** "Zero (explicit)-copy" interface (can never hide all bus delays)
* Write-combining memory (configured via [[MTRR|MTRRs]] or [[Page Attribute Tables|PATs]]) avoids PCI snoop requirements and maximizes linear throughput
** Subtle side-effects; not to be used glibly or carelessly!
* Distributes work at ''block'' granularity to [[#Texture Processing Cluster|Texture Processing Clusters]] (TPCs).
====Texture Processing Cluster====
[[#Streaming Multiprocessors|Streaming Multiprocessors]] (SMs) are grouped into TPCs. Each TPC contains some number of SMs and a single texture processing unit, including a few filters and a cache for texture memory. The details of these texture caches have not generally been publicized, but NVIDIA optimization guides confirm 1- and 2-dimensional spatial caching to be in effect.

===Streaming Multiprocessor===
* Each SM has a register file, fast local (''shared'') memory, a cache for constant memory, an instruction cache (ROP), a multithreaded instruction dispatcher, and some number of [[#Stream Processor|Stream Processors]] (SPs).
** 8192 registers for compute capability <= 1.1, otherwise
** 16384 for compute capability <= 1.3
* A group of threads which share a memory and can "synchronize their execution to coördinate accesses to memory" (use a [[barrier]]) form a '''block'''. Each thread has a ''threadId'' within its (three-dimensional) block.
** For a block of dimensions <Dx, Dy, Dz>, the threadId of the thread having index <x, y, z> is (x + y * Dx + z * Dy * Dx).
* Register allocation is performed per-block, and rounded up to the nearest
** 256 registers per block for compute capability <= 1.1, otherwise
** 512 registers per block for compute capability <= 1.3.
* A group of blocks which share a kernel form a '''grid'''. Each block (and each thread within that block) has a ''blockId'' within its (two-dimensional) grid.
** For a grid of dimensions <Dx, Dy>, the blockId of the block having index <x, y> is (x + y * Dx).
* Thus, a given thread's <blockId X threadId> dyad is unique across the grid. All the threads of a block share a blockId, and corresponding threads of various blocks share a threadId.
* Each time the kernel is instantiated, new grid and block dimensions may be provided.
* A block's threads, starting from threadId 0, are broken up into contiguous '''warps''' having some '''warp size''' number of threads.
* Distributes out-of-order work at ''warp'' granularity across [[#Stream Processor|SPs]].
** One program counter per warp -- divergence within warp leads to serialization.
** Divergence is trivially supported with a per-warp stack; warps reconverge at [[Compiler Design|immediate post-dominators]] of branches
* Supports some maximum number of blocks and threads (~8 and ~768 on G80).
====Block sizing====
'''FIXME: review/verify this!'''

How tightly can we bound the optimal block size '''T''', given a warp size ''w''? The number of threads per block ought almost always be a multiple of ''w'', both to:
* facilitate coalescing (coalescing requirements are related to ''w/2''), and
* maximize utilization of SPs within warp-granular scheduling.
A SM has ''r'' registers and ''s'' words of shared memory, allocated per-block (see [[#Streaming Multiprocessors|above]]). Assuming that ''w'' threads can be supported (i.e., that none requires more than ''r/w'' registers or ''s/w'' words of shared memory), the most obvious lower bound is ''w'' itself. The most obvious upper bound, assuming arbitrary available work, is the greatest multiple of ''w'' supported by hardware (and, obviously, the SDK). A block must be scheduled to an SM, which requires:
* registers sufficient to support the block,
* shared memory sufficient to support the block,
* that the total number of threads not exceed some limit ''t'' (likely bounding the divergence-tracking stacks), and
* that the total number of blocks not exceed some limit ''b'' (likely bounding the warp-scheduling complexity).
A given SM, then, supports '''T''' values through the minimum of {''r''/'''Thrreg''', ''s''/'''Blkshmem''', and ''t''}; as the block requires fewer registers and less shared memory, the upper bound converges to ''t''.

Motivations for larger blocks include:
* freedom in the ''b'' dimension exposes parallelism until ''t'' <= ''b'' * '''T'''
* larger maximum possible kernels (an absolute limit exists on grid dimensions)
* better if data can be reused among threads (e.g. in tiled matrix multiply)
Motivations for smaller blocks include:
* freedom in the ''t'' dimension exposes parallelism until ''t'' >= ''b'' * '''T'''
* freedom in the ''r'' and ''s'' dimensions exposes parallelism until ''r'' >= ''b'' * '''T''' * '''Thrreg''' or ''s'' >= ''b'' * '''Blkshmem'''.
* cheaper per-block operations(?) (<tt>__syncthreads()</tt>, voting, etc)
* support for older hardware and SDKs
* fairer distribution among SMs and thus possibly better utilization, lower latency
** relative speedup tends to 0 as work grows arbitrarily on finite SMs
** relative speedup tends to ''1/Fracpar'' on infinitely many SMs
We can now optimize occupancy for a specific {''t'', ''b'', ''r'' and ''s''}, assuming ''t'' to be a multiple of both ''w'' and ''b'':
* Let '''T''' = ''t'' / ''b''. '''T''' is thus guaranteed to be the smallest multiple of ''w'' such that ''t'' == ''b'' * '''T'''.
* Check the ''r'' and ''w'' conditions. '''FIXME: handle reduction'''
* '''FIXME: handle very large (''external'') kernels'''
Optimizing for ranges of hardware values is left as an exercise for the reader. Occupancy is only worth optimizing if the number of warps are insufficient to hide latencies. It might be possible to eliminate latencies altogether by reusing data throughout a block via shared memory; if the algorithm permits, this is almost certainly a net win. In that case, we likely want to maximize '''Blkshmem'''. A more advanced theory would incorporate the arithmetic intensity of a kernel...'''FIXME'''

===Stream Processor===
* In-order, multithreaded processor: memory latencies can be hidden only by TLP, not ILP.
** '''UPDATE''' Vasily Volkov's awesome GTC 2010 paper, "[http://www.cs.berkeley.edu/~volkov/volkov10-GTC.pdf Better Performance at Lower Occupancy]", ''destroys'' this notion.
*** Really. Go read Vasily's paper. It's better than anything you'll find here.
** Arithmetic intensity and parallelism are paramount!
** Memory-bound kernels require sufficiently high ''occupancy'' (the ratio of concurrently-running warps to maximum possible concurrent warps (as applied, usually, to [[#Streaming Multiprocessor|SMs]])) to hide latency.
* No branch prediction or speculation (and thus also no pipeline flushes on mispredicted branches).
{| border="1"
! Memory type
! PTX name
! Sharing
! Kernel access
! Host access
! Cache location
! Adddressable
|-
| Registers
| .reg
| Per-thread
| Read-write
| None
| None
| No
|-
| Special registers
| .sreg
| varies
| Read-only
| None
| None
| No
|-
| Local memory
| .local
| Per-thread
| Read-write
| None
| None
| Yes
|-
| Shared memory
| .shared
| Per-block
| Read-write
| None
| None
| Yes
|-
| Global memory
| .global
| Global
| Read-write
| Read-write
| '''1.x''': None
'''2.0+''': L1 on SM, L2 on TPC(?)
| Yes
|-
| Constant memory
| .const
| Per-grid
| Read
| Read-write
| Stream multiprocessor
| Yes
|-
| Texture memory
| .tex
| Global
| Read
| Read-write
| Texture processing cluster
| texture API
|-
| Parameters (to grids or functions)
| .param
| Per-grid (or per-thread)
| Read-only (or read-write)
| None
| None
| Yes (or restricted)
|-
|}

===Compute Capabilities===
The original public CUDA revision was 1.0, implemented on the NV50 chipset corresponding to the GeForce 8 series. Compute capability, formed of a non-negative major and minor revision number, can be queried on CUDA-capable cards. All revisions thus far have been backwards-compatible.
{| border="1" class="wikitable"
! Resource
! 1.0 SM
! 1.1 SM
! 1.2 SM
! 1.3 SM
! 2.0 SM
! 2.1 SM
! 3.0 SMX
|-
|CUDA cores
|8
|8
|8
|8
|32
|48
|192
|-
|Warp schedulers
|1
|1
|1
|1
|2
|2
|4
|-
|Insts/sched
|1
|1
|1
|1
|1
|2
|2
|-
|Threads
|768
|768
|1024
|1024
|1536
|1536
|2048
|-
|Warps
|24
|24
|32
|32
|48
|48
|64
|-
|Blocks
|8
|8
|8
|8
|8
|8
|16
|-
|32-bit registers
|8192
|8192
|16384
|16384
|32768
|32768
|65536
|-
}
{| border="1"
! Revision
! Changes
|-
| 1.1
|
* Atomic ops on 32-bit global integers.
* Breakpoints and other debugging support.
|-
| 1.2
|
* Atomic ops on 64-bit global integers and 32-bit shared integers.
* 32 warps (1024 threads) and 16K registers per multiprocessor (MP).
* Vote instructions.
* Three MPs per Texture Processing Cluster (TPC).
* Relaxed memory coalescing constraints.
|-
| 1.3
|
* Double-precision floating point at 32 cycles per operation.
|-
| 2.0
|
* 32 cores per SM
* 4 SFUs
* Atomic addition on 32-bit global and shared FP.
* 48 warps (1536 threads), 48K shared memory banked 32 ways, and 32K registers per MP.
* 512K local memory per thread.
* <tt>__syncthreads_{count,and,or}()</tt>, <tt>__threadfence_system()</tt>, and <tt>__ballot()</tt>.
* 1024 threads per block and <tt>blockIdx.{x,y}</tt> values ranging through 1024.
* Larger texture references.
* ''PTX 2.0''
** Efficient uniform addressing (<tt>ldu</tt>)
** Unified address space: <tt>isspacep</tt>/<tt>cvta</tt>
** Prefetching: <tt>prefetch</tt>/<tt>prefetchu</tt>
** Cache modifiers on loads and stores: <tt>.ca</tt>, <tt>.cg</tt>, <tt>.cs</tt>, <tt>.lu</tt>, <tt>.cv</tt>
** New integer ops: <tt>popc</tt>/<tt>clz</tt>/<tt>bfind</tt>/<tt>brev</tt>/<tt>bfe</tt>/<tt>bfi</tt>
** Video ops: <tt>vadd</tt>, <tt>vsub</tt>, <tt>vabsdiff</tt>, <tt>vmin</tt>, <tt>vmax</tt>, <tt>vshl</tt>, <tt>vshr</tt>, <tt>vmad</tt>, <tt>vset</tt>
** New special registers: <tt>nsmid</tt>, <tt>clock64</tt>, ...).
|-
| 2.1
|
* 48 cores per SM
* 8 SFUs per SM, 8 TFUs per ROP
* 2 warp schedulers per SM, capable of issuing two instructions per clock
|-
| 3.0
|
* 192 cores per SMX
* 32 SFUs per SMX, 32 TFUs per ROP
* 4 warp schedulers per SMX, capable of issuing two instructions per clock
* ''PTX 3.0''
** <tt>madc</tt> and <tt>mad.cc</tt> instructions
** Cubemaps and cubearrays for the <tt>tex</tt> instruction
** 3D surfaces via the <tt>suld.b.3d</tt> and <tt>sust.b.3d</tt> instructions
** <tt>pmevent.mask</tt> to trigger multiple performance counters
** 64-bit grid IDs
** 4 more performance counters, for a total of 8
** DWARF debugging symbols support

|-
|}

==PTX==
===Syntax Coloring===
[[File:ptxcolor.png|thumb|right|PTX with syntax coloring]]
I've got a [[vim]] syntax coloring file for PTX/NVIR/SASS at https://raw.github.com/dankamongmen/dankhome/master/.vim/syntax/nvir.vim. It operates by coloring all registers congruent to some integer mod 10 the same color:
<pre>syn match asmReg0 "v\?R[0-9]*0$\.B\|\.F\|\.U\?\(I\|L$\|$[^0-9]$\@=\)"
syn match asmReg1 "v\?R[0-9]*1$\.B\|\.F\|\.U\?\(I\|L$\|$[^0-9]$\@=\)"
syn match asmReg2 "v\?R[0-9]*2$\.B\|\.F\|\.U\?\(I\|L$\|$[^0-9]$\@=\)"
syn match asmReg3 "v\?R[0-9]*3$\.B\|\.F\|\.U\?\(I\|L$\|$[^0-9]$\@=\)"
syn match asmReg4 "v\?R[0-9]*4$\.B\|\.F\|\.U\?\(I\|L$\|$[^0-9]$\@=\)"
syn match asmReg5 "v\?R[0-9]*5$\.B\|\.F\|\.U\?\(I\|L$\|$[^0-9]$\@=\)"
syn match asmReg6 "v\?R[0-9]*6$\.B\|\.F\|\.U\?\(I\|L$\|$[^0-9]$\@=\)"
syn match asmReg7 "v\?R[0-9]*7$\.B\|\.F\|\.U\?\(I\|L$\|$[^0-9]$\@=\)"
syn match asmReg8 "v\?R[0-9]*8$\.B\|\.F\|\.U\?\(I\|L$\|$[^0-9]$\@=\)"
syn match asmReg9 "v\?R[0-9]*9$\.B\|\.F\|\.U\?\(I\|L$\|$[^0-9]$\@=\)"
syn match asmPReg "P[0-9]$[0-9]*$$\.B\|\.F\|\.U\?\(I\|L$\|$[^0-9]$\@=\)"
syn match asmBB "BB[0-9][0-9]*$_\d\d*$\?"
syn match asmBBNew "BB-\d\d*"
syn match nvirNT ".NEXT_TRUE.*"
syn match nvirNF ".NEXT_FALSE.*"
syn match hexconst "0x\x\+$\.F\|\.U\?\(I\|L$\)\?"
syn match spreg "$ctaid\|ntid\|tid\|nctaid$.$x\|y\|z$"</pre>

==Building CUDA Apps==
===nvcc flags===
* <tt>-ptax-options=-v</tt> displays per-thread register usage
===SDK's common.mk===
This assumes use of the SDK's common.mk, as recommended by the documentation.
* Add the library path to LD_LIBRARY_PATH, assuming CUDA's been installed to a non-standard directory.
* Set the <tt>CUDA_INSTALL_PATH</tt> and <tt>ROOTDIR</tt> (yeargh!) if outside the SDK.
* I keep the following in <tt>bin/cudasetup</tt> of my home directory. Source it, using sh's <tt>. cudasetup</tt> syntax:
<pre>CUDA="$HOME/local/cuda/"

export CUDA_INSTALL_PATH="$CUDA"
export ROOTDIR="$CUDA/C/common/"
if [ -n "$LD_LIBRARY_PATH" ] ; then
export "LD_LIBRARY_PATH=$LD_LIBRARY_PATH:$CUDA/lib64"
else
export "LD_LIBRARY_PATH=$CUDA/lib64"
fi

unset CUDA</pre>
* Set EXECUTABLE in your Makefile, and include <tt>$CUDA_INSTALL_PATH/C/common/common.mk</tt>
====Unit testing====
The <tt>DEFAULT_GOAL</tt> special variable of [[GNU Make]] can be used:
<pre>.PHONY: test
.DEFAULT_GOAL:=test

include $(CUDA_INSTALL_PATH)/C/common/common.mk

test: $(TARGET)
$(TARGET)</pre>

==Libraries==
Two mutually exclusive means of driving CUDA are available: the "Driver API" and "C for CUDA" with its accompanying <tt>nvcc</tt> compiler and runtime. The latter (<tt>libcudart</tt>) is built atop the former, and requires its <tt>libcuda</tt> library.
===Undocumented Functions===
The following unlisted functions were extracted from 3.0's libcudart.so using <tt>objdump -T</tt>:<pre>00000000000097d0 g DF .text 000000000000020e Base __cudaRegisterShared
0000000000005410 g DF .text 0000000000000003 Base __cudaSynchronizeThreads
0000000000009e60 g DF .text 0000000000000246 Base __cudaRegisterVar
000000000000a0b0 g DF .text 0000000000000455 Base __cudaRegisterFatBinary
00000000000095c0 g DF .text 000000000000020e Base __cudaRegisterSharedVar
0000000000005420 g DF .text 0000000000000002 Base __cudaTextureFetch
000000000000a510 g DF .text 00000000000009dd Base __cudaUnregisterFatBinary
00000000000099e0 g DF .text 000000000000024e Base __cudaRegisterFunction
0000000000005820 g DF .text 000000000000001c Base __cudaMutexOperation
0000000000009c30 g DF .text 000000000000022e Base __cudaRegisterTexture</pre>

==deviceQuery info==
* Memory shown is that amount which is free; I've substituted total VRAM.
* Most CUDA devices can switch between multiple frequencies; the "Clock rate" output ought be considered accurate only at a given moment, and the outputs listed here are merely illustrative.
* Three device modes are currently supported:
** 0: Default (multiple applications can use the device)
** 1: Exclusive (only one application may use the device; other calls to <tt>cuCtxCreate</tt> will fail)
** 2: Disabled (no applications may use the device; all calls to <tt>cuCtxCreate</tt> will fail
* The mode can be set using <tt>nvidia-smi</tt>'s -c option, specifying the device number via -g.
* A run time limit is activated by default if the device is being used to drive a display.
* Please feel free to [mailto:nickblack@acm.org send me output!]
{| border="1"
! Device name
! Memory
! MP's
! Cores
! Const mem
! Shmem/block
! Reg/block
! Warp size
! Thr/block
! Max pitch
! Texalign
! Clock
! C+E?
! Integrated?
! Shared maps?
|-
! COLSPAN="15" style="background:#8070D8;" | Compute capability 3.0
|-
| GeForce GTX 680
| 1.5GB
| 8
| 1536
|
|
| 32
| 1024
|
|
|
|
|
| No
| Yes
|-
! COLSPAN="15" style="background:#ffdead;" | Compute capability 2.1
|-
| GeForce GTX 460
| 1GB
| 7
| 224
| 64k
| 48k
| 32k
| 32
| 1024
| 2G
| 512b
| 1.35GHz
| 2x
| No
| Yes
|-
! COLSPAN="15" style="background:#ffdead;" | Compute capability 2.0
|-
| GeForce GTX 580
| 1.5GB
| 16
| 512
| 1536
|
|
|
| 32
| 1024
|
|
|
| No
| Yes
|-
| Tesla C2050 (*CB)
| 3GB
| 14
| 448
| 64k
| 48k
| 32k
| 32
| 1024
| 2G
| 512b
| 1.15GHz
| 2x
| No
| Yes
|-
| Tesla C2070 (*CB)
| 6GB
| 14
| 448
| 64k
| 48k
| 32k
| 32
| 1024
| 2G
| 512b
| 1.15GHz
| 2x
| No
| Yes
|-
| GeForce GTX 480
| 1536MB
| 15
| 480
|
|
|
|
|
|
|
|
|
|
|
|-
| GeForce GTX 470
| 1280MB
| 14
| 448
|
|
|
|
|
|
|
|
|
|
|
|-
! COLSPAN="15" style="background:#efefef;" | Compute capability 1.3
|-
| Tesla C1060
| 4GB
| 30
| 240
| 65536b
| 16384b
| 16384
| 32
| 512
| 262144b
| 256b
| 1.30GHz
| Yes
| No
| Yes
|-
| GeForce GTX 295
| 1GB
| 30
| 240
| 65536b
| 16384b
| 16384
| 32
| 512
| 262144b
| 256b
| 1.24GHz
| Yes
| No
| Yes
|-
| GeForce GTX 285
| 1GB
| 30
| 240
| 65536b
| 16384b
| 16384
| 32
| 512
| 262144b
| 256b
| 1.48GHz
| Yes
| No
| Yes
|-
| GeForce GTX 280
| 1GB
| 30
| 240
| 65536b
| 16384b
| 16384
| 32
| 512
| 262144b
| 256b
| 1.30GHz
| Yes
| No
| Yes
|-
| GeForce GTX 260
| 1GB
| 27
| 216
| 65536b
| 16384b
| 16384
| 32
| 512
| 262144b
| 256b
| 1.47GHz
| Yes
| No
| Yes
|-
! COLSPAN="15" style="background:#efefef;" | Compute capability 1.2
|-
| GeForce GT 360M
| 1GB
| 12
| 96
| 65536b
| 16384b
| 16384
| 32
| 512
| 262144b
| 256b
| 1.32GHz
| Yes
| No
| Yes
|-
| GeForce 310
| 512MB
| 2
| 16
| 65536b
| 16384b
| 16384
| 32
| 512
| 262144b
| 256b
| 1.40GHz
| Yes
| No
| Yes
|-
| GeForce 240 GT
| 1GB
| 12
| 96
| 65536b
| 16384b
| 16384
| 32
| 512
| 262144b
| 256b
| 1.424GHz
| Yes
| No
| Yes
|-
! COLSPAN="15" style="background:#efefef;" | Compute capability 1.1
|-
| ION
| 256MB
| 2
| 16
| 65536b
| 16384b
| 8192
| 32
| 512
| 262144b
| 256b
| 1.1GHz
| No
| Yes
| Yes
|-
| Quadro FX 570
| 256MB
| 2
| 16
| 65536b
| 16384b
| 8192
| 32
| 512
| 262144b
| 256b
| 0.92GHz
| Yes
| No
| No
|-
| GeForce GTS 250 (*JR)
| 1G
| 16
| 128
| 65536b
| 16384b
| 8192
| 32
| 512
| 2147483647b (!)
| 256b
| 1.84GHz
| Yes
| No
| No
|-
| GeForce 9800 GTX
| 512MB
| 16
| 128
| 65536b
| 16384b
| 8192
| 32
| 512
| 262144b
| 256b
| 1.67GHz
| Yes
| Yes
| Yes
|-
| GeForce 9600 GT
| 512MB
| 8
| 64
| 65536b
| 16384b
| 8192
| 32
| 512
| 262144b
| 256b
| 1.62GHz,
1.50GHz
| Yes
| No
| No
|-
| GeForce 9400M
| 256MB
| 2
| 16
| 65536b
| 16384b
| 8192
| 32
| 512
| 262144b
| 256b
| 0.88GHz
| No
| No
| No
|-
| GeForce 8800 GTS 512
| 512MB
| 16
| 128
| 65536b
| 16384b
| 8192
| 32
| 512
| 262144b
| 256b
| 1.62GHz
| Yes
| No
| No
|-
| GeForce 8600 GT
| 256MB
| 4
| 32
| 65536b
| 16384b
| 8192
| 32
| 512
| 262144b
| 256b
| 0.95GHz
| Yes
| No
| No
|-
| GeForce 9400M
| 512MB
| 1
| 8
| 65536b
| 16384b
| 8192
| 32
| 512
| 262144b
| 256b
| 1.40GHz
| No
| No
| No
|-
|}
(*CB) Thanks to Cameron Black for this submission!
(*JR) Thanks to Javier Ruiz for this submission!

==See Also==
* The nouveau Wiki's [http://nouveau.freedesktop.org/wiki/CUDA CUDA page]
** [http://nouveau.freedesktop.org/wiki/HonzaHavlicek Honza Havlicek]'s guide to NVIDIA architecture
** [http://nouveau.freedesktop.org/wiki/ContextSwitching Context switching] and the PSWITCH instruction
* The [http://code.google.com/p/gpuocelot/ gpuocelot] project, hosted on Google Code.
* The NVIDIA [http://developer.nvidia.com/object/gpucomputing.html GPU Developer Zone]
* My [[CUBAR]] tools and reverse-engineered [[libcudest]]
[[CATEGORY: GPGPU]]

Fonts

2012-05-07T08:59:56Z

Dank: Created page with "Fonts can be installed by copying the appropriate .otf or .ttf file to ~/.fonts. Some fonts worth checking out: ==Inconsolata== * http://levien.com/type/myfonts/inconsolata.h..."

Fonts can be installed by copying the appropriate .otf or .ttf file to ~/.fonts. Some fonts worth checking out:

==Inconsolata==
* http://levien.com/type/myfonts/inconsolata.html
* http://www.google.com/webfonts/specimen/Inconsolata
==Consolas==
* http://www.microsoft.com/en-us/download/details.aspx?id=17879
==Monaco==
* http://www.gringod.com/wp-upload/software/Fonts/Monaco_Linux.ttf

Omphalos

2012-05-07T05:32:02Z

Dank:

[[File:omphalos.png|right]]
[[File:omphalos-2011-12-01.jpg|thumb|right|Three omphalos processes, 2011-12-01]]
A tool for network enumeration, protection, observation and domination. Omphalos makes use of passive and active portscanning, DNS/DHCP/[[Zeroconf]] server interrogation, portknock detection, covert channel detection and establishment, ARP scanning, automatic WEP cracking, man-in-the-middling, and a whole host of other tricks. GPS integration? Oh yes. Coordination across multiple interfaces? Of course. Use of Linux's MMAP_RX_SOCKET and MMAP_TX_SOCKET? Wouldn't have it any other way. Userspace networking is made visible to the host via a [[TUN/TAP]] device. While designed as an offensive tool, omphalos has proven useful for network debugging and troubleshooting, as well as experimentation.

'''The latest release is [http://dank.qemfd.net/src/omphalos/rel/current/ 0.99.0 (β)], released 2011-12-01.'''

Omphalos is not a "''point-and-click''" tool so much as "''pull the pin''" or perhaps "''spray the area''". Default behavior is to redirect and seize all traffic, attack weak cryptosystems, archive authentication materials, and learn everything that can be learned. Ideally, a tiny microprocessor would be paired with power and a network device, stealthily physically inserted into a network, and left there; <tt>omphalos</tt> and [[Hackery#liburine|liburine]] would then combine to provide complete network dominance. I hope to combine network programming and high-performance computing to create a tool capable of much havoc.

'''Omphalos: Because one layer is never enough.''' Code is hosted on [https://github.com/dankamongmen/omphalos GitHub]. Bugtracking is hosted on [http://dank.qemfd.net/bugzilla/buglist.cgi?cmdtype=runnamed&namedcmd=omphalos qemfd-bugzilla]. There's a mailing list at [http://groups.google.com/group/omphalos-dev Google Groups].
==Similar Tools==
* [http://www.thoughtcrime.org/software/sslsniff/ SSLSNIFF] from Thoughtcrime Labs
* [http://ettercap.sourceforge.net/ ettercap] by Alberto Ornaghi and Marco Valleri
* [http://www.nixgeneration.com/~jaime/netdiscover/ Netdiscover] by Jaime Peñalba
* [http://www.netresec.com/?page=NetworkMiner NetworkMiner] from NETRESEC AB
* [http://www.jdisc.com/ JDisc Discovery] from JDisc UG
* [http://www.lantopolog.com/ LanTopolog] by Yuriy Volokitin
* [http://code.google.com/p/mirandaupnptool/ Miranda] by Craig Heffner
===Countertools===
We want to defeat systems like:
* [http://arpon.sourceforge.net/ ArpON] by Andrea Di Pasquale et al
===Subsumed Tools===
Omphalos implements all or portions of the functionality of the following tools:
* [[Avahi]], the linux [[zeroconf]] daemon
* [http://www.litech.org/radvd/ radvd], the linux IPv6 Router Advertisement daemon

==Versions/Milestones/Releases==
{| border="1" class="wikitable"
! Version
! Release date
! Features
|-
|0.98 (initial alpha)
|'''[https://github.com/dankamongmen/omphalos/tree/v0.98alpha 2011-10-07]''' (actual)
2011-09-23 (planned)
|
*Detection of network entities at layers 2 and 3.
*Dynamic handling of devices, routes, neighbors and addresses
*Full [[netlink]], ethtool, nl80211 and wireless extensions support
*TTY and [[ncurses]]-based UI's
*[[ARP]]- and [[DNS]]-based probing
|-
|0.99.0β (initial beta)
|'''[https://github.com/dankamongmen/omphalos/tree/v0.99.0β 2011-12-01]''' (actual)
2011-11-11 (planned)
|
*Routing/iptables configuration capabilities
*Hostapd and AP-spoofing support
*Spoofing support at layers 2 and 3
*[[Zeroconf]]- and WINS-based probing
|-
|1.0
|2011-12-25 (planned)
|
*Automated selection and execution of previous capabilities
*GPS support
*Logging support
*[[Topology Discovery|LLTD]] and some [[NetBIOS]] support
|}

==General Features==
Some planned, some implemented...
* Modes of operation governing automatic behavior, from "Silent" to "Hostile":
{| border="1" class="wikitable"
! Mode
! Summary
! Operating characteristics
|-
| Silent
| Take no actions, only watch.
|
* TX ringbuffers/sockets are not automatically created
* No packets will be issued by omphalos unless requested
* No automatic modifications to host networking state
|-
| Stealthy
| Take only the actions of a normally-configured host.
|
* [[ARP]] queries will be automatically issued
* [[DNS]] and [[Zeroconf]] queries will be issued, but only as the host is configured
* No automatic modifications to host networking state
|-
| Active
| Learn what we can, possibly standing out from the crowd.
|
* Make free use of detected information for further recon
* No automatic modifications to host networking state
|-
| Aggressive
| Learn things quickly, in ways that will be noticed.
|
* "Active", plus...
* Periodic and triggered wide-spectrum active scanning
* Omphalos will freely manipulate host networking state
|-
| Forceful
| Actively disrupt the network, rerouting traffic through us.
|
* Continuous scanning of the network
* MitM automatically effected wherever possible
* DoS will be employed to make MitM more effective
* Omphalos will freely manipulate host networking state
|-
| Hostile
| Attempt to make the network unusable.
|
* Same as "Forceful", but don't pass traffic along once MitM'd.
* Actively employ null routing.
* DoS employed upon network infrastructure, carrier, and and egress.
|-
|}
* GPS coordination and tagging
* Fully dynamic behavior viz the networking stack. Add and remove cards, routes, addresses...
* Audiovisual plugins ('''FIXME''' detail! lots of good ideas here)
* Event/scripting engine
** Fine-grained MitM packet manipulation, filtering and generation via [[Hackery#parvenu|Parvenu]] and domain-specific languages
** Fine-grained, one-click identity theft at any desired layer(s) (assumption of MAC, IP, cookies, etc)
*** Eat your heart out, [http://codebutler.com/firesheep Firesheep]!
* Full integration with [[Linux_APIs#POSIX_capabilities|POSIX capabilities]] for fine-grained security (nothing runs as the superuser)
* Covert channel detection at all layers via [[Hackery#Zetetic|Zetetic]]
* Opportunistic, secure remote control via [[Hackery#liburine|liburine]]
===Network Analysis===
* Network analysis and debugging ought be spun out into [[Hackery#drbenway|Dr. Benway]]
{| class="wikitable" border="1"
! Layer
! Subdivisions
! What's tracked
! Notes
|-
| Layer 2
| From both packets and netlink:
* VLANs
* ESSs
|
* Nodes from packets:
** All source hardware addresses seen in packets
** All destination hardware multicast addresses
* Nodes from netlink:
** All hardware addresses in the kernel neighbor cache
** Our hardware addresses
** Hardware broadcast addresses
|
* Node allocation is backed by a mainly-static [[VLHU]]
** At the point an attacker can overwhelm our VLHU, there's effectively nothing on the network but junk packets.
* If something's a source, it's being claimed as present here on the network. A destination means nothing, except in the case of multicast.
* Someone else sending with our MAC address ought be noted, unless we stole their MAC address
* We can't generally differentiate between two other physical hosts using the same MAC
** Multiple interfaces might actually be sharing a MAC intentionally for low-latency failover
** Upshot: we don't/can't care. We only care if someone else uses *our* MAC (unless told it's ok).
* We can't detect a spoofed MAC, but we can send our own ARP probes and at least determine whether the MAC's being serviced
|-
| Layer 3
| From both packets and netlink:
* Networks
|
We don't want to track network addresses beyond our broadcast domain. That's difficult to determine, however, without a working routing configuration (ie, an address). We'll thus assume that RFC1918 membership or service of an L2-restricted service (like [[DHCP]] or [[Zeroconf]]) indicates local presence (if it doesn't, it indicates misconfiguration). This means that
* Hosts from netlink:
** All network addresses in the kernel neighbor cache
** Configured router addresses
** Our configured network addresses
** Configured broadcast addresses
* Hosts from packets:
** All source network addresses from the RFC1918 networks
** All source network addresses to which we have a configured route
** All source network addresses observed offering L2-restricted services
*** All routers and nameservers named in a DHCP packet
** All destination network multicast addresses
|
* Host allocation is backed by a dynamic [[VLHU]].
* More dynamic and larger VLHU than that for layer 2, since we can have more hosts than nodes -- imagine a /0 route configuration sitting on an internet backbone. Small implementations of ARP tables and CAMs in nodes/switches means, say, 4k nodes ought almost always be sufficient for any interface.
* Multiple nodes can share a host address, but it can also indicate a problem
* Other nodes using *our* host addresses is a problem unless told otherwise
* Seeing an L3 address on a MAC means either:
** There's another network present locally (if we have no route to the L3, and the MAC responds to an [[ARP]] query for the L3), or
** That MAC is routing to that address (if the MAC is associated with a route to the L3), or
** That MAC serves that address (if we have a local route to the address)
*** Perhaps only temporarily, and perhaps without service provision (eg DHCP requests), or
** There's any variety of misconfiguration/failure/adversary at work (le sigh)
* Upshot: we can discover the local network(s) without relying on any configuration, even those which don't advertise (ie with [[DHCP]])
|-
| Layer 4
|
| From packets:
* DNS and DHCP servers
| We don't use the local configuration because there's no unified API to access it, nor track changes to it. We'll detect DNS quickly enough if anything's actually using the network, and can partially detect host DNS servers simply by kicking off a query through the standard resolver library (even if we don't use the provided result).
|-
|}

==Analysis and Attack Capabilities==
===Physical Layer Support===
{| class="wikitable" border="1"
! Protocol
! [[Standards|Standard]]
! [[Pcap|libpcap]] linktype
! Linux ARP type
! Analyzed?
|-
| BSD Loopback
| ?
| DLT_NULL
| N/A
| No
|-
| Linux Cooked Capture
| [http://linuxmanpages.com/man7/packet.7.php packet(7)]
| DLT_LINUX_SLL
| N/A
| Yes
|-
| [[Ethernet]]
* Ethernet II/DIX
* Novell 802.3
* IEEE 802.2 LLC
* SNAP
* 802.1Q VLAN/802.1p QoS (IEEE 802.3ac)
| IEEE 802.3-2008
| DLT_EN10MB
| ARPHRD_ETHER
| Yes
|-
| Token Ring
| IEEE 802.5
| DLT_IEEE802
| ARPHRD_IEEE802_TR
| No
|-
| ARCNET
| ANSI 878.1
|
* DLT_ARCNET
* DLT_ARCNET_LINUX
| ARPHRD_ARCNET
| No
|-
| SLIP
(Serial Line Internet Protocol)
|
* RFC 1055 (SLIP)
* RFC 1154 (CSLIP)
| DLT_SLIP
|
* ARPHRD_SLIP
* ARPHRD_SLIP6
* ARPHRD_CSLIP
* ARPHRD_CSLIP6
| No
|-
| PPP (Point-to-Point Protocol)
* BSD/OS PPP
* PPP over serial
* PPPoE (PPP over [[Ethernet]])
* PPPoA (PPP over ATM)
* Cisco PPP/HDLC
| RFC 1661
* ?
* RFC 1662
* RFC 2516
* RFC 2364
* RFC 1547
| DLT_PPP
* DLT_PPP_BSDOS
* DLT_PPP_SERIAL
* DLT_PPP_ETHER
* ?
* DLT_C_HDLC
| ARPHRD_PPP
| Partial
* No
* No
* No
* No
* Yes
|-
| FDDI
(Fiber Distributed Data Interface)
|
* MAC: ANSI X3.139-1987 / ISO 9314-2
* PHY: ANSI X3.148-1988 / ISO 9314-1
| DLT_FDDI
| ARPHRD_FDDI
| No
|-
| Fibre Channel
| RFC 2625
| DLT_IP_OVER_FC
|
* ARPHRD_FCPP
* ARPHRD_FCAL
* ARPHRD_FCPL
* ARPHRD_FCFABRIC
| No
|-
| IrDA
(Infrared Data Association)
|
* IrDA PHY Spec v1.5
* IrDA Link Access Protocol v1.1
| DLT_LINUX_IRDA
| ARPHRD_IRDA
| Yes
|-
| Radiotap
| De facto
| DLT_IEEE802_11_RADIO
| ARPHRD_IEEE80211_RADIOTAP
| Yes
|-
| Firewire
| IEEE 1394
| N/A
| ARPHRD_IEEE1394
| Yes
|-
| Frame Relay
| ?
| DLT_FRELAY
| ARPHRD_FRAD
| No
|-
| Apple LocalTalk
| ?
| DLT_LTALK
| ARPHRD_APPLETLK
| No
|-
| LAPD
(Link Access Protocol - D Channel)
| ITU Q.921
| DLT_LINUX_LAPD
| ARPHRD_LAPB
| No
|-
|}

===Layer 2===
====Topology Discovery====
''For more information, see the [[Topology Discovery]] page.''
{| class="wikitable" border="1"
|-
! Protocol
! Standard
! Support
|-
| [[Topology_Discovery#Link-Local_Topology_Discovery_.28LLTD.29_Protocol|LLTDP]]
| Microsoft
|
* Extraction of data from HELLO packets
* Enumeration via DISCOVERY requests
|-
| [[Topology_Discovery#Link-Layer_Discovery_Protocol_.28LLDP.29|LLDP]]
| IEEE 802.1AB-2005
|
* None yet
|-
| [[Topology_Discovery#Cisco_Discovery_Protocol_.28CDP.29|CDP]]
| Cisco
|
* None yet
|-
| STP
| IEEE 802.1D
|
* Minimal analysis of BDPUs
|-
|}
====802.3/Ethernet II====
* Detect physical hosts on the network via MAC analysis
** Classify as locally-generated, multicast, etc
* Flood a network with spoofed MAC addresses, in the hope of forcing fail-open behavior to facilitate attacks (see <tt>macof</tt> from [http://monkey.org/~dugsong/dsniff/ dsniff] and ''Hacking Layer 2: Fun with Ethernet Switches'' from BlackHat 2002)
* Probe and autodetect CAM sizes and hash functions, allowing for minimal CAM overflows
* Autodetect host [[ARP]] timings and replacement policies, allowing for stealthy man-in-the-middling
* Reverse and direct man-in-the-middling (answer all queries for an address, from an address, or both)
* Gratuitous ARP ("enclosure")
* Controlled SNAT of outgoing traffic at layer 2, to create multiple realistic hosts ("Capgras delusions")
* Automated [[ARP]] jamming and man-in-the-middling
* [http://en.wikipedia.org/wiki/Arpwatch Arpwatch-like] layer 2 monitoring
* VLAN hopping

====802.11====
* Passively attack weak cryptosystems (especially WEP), or do so actively if configured
* Channel hopping or locked operation
* Spectrum and noise analysis plugin
* Respond as master to probed networks, on a to-order basis
* Ability to run omphalos in as an AP client via userspace networking atop radiotap (Monitor mode) and WPA/EAPOL support
** Or, more likely, some kind of hostapd control using Master mode
* "[http://www.airtightnetworks.com/WPA2-Hole196 Hole 196]" injection
* Viehbock's [http://sviehb.files.wordpress.com/2011/12/viehboeck_wps.pdf WPS EAP-NACK] brute-force attack ([http://www.kb.cert.org/vuls/id/723755 US-CERT #723755])

===Layer 3===
* ICMP redirects
** We're closer than the remote server; jam ours in, and let the real one be tossed as duplicate
* A whole world of IPv6 mischief
* Rogue DHCP service
* SNAT for routing enbondaged neighbors
* ...much more

===Layer 4===
* TCP assassination (via RST) / arbitrary corruption
** Most [[TCP]] implementations will (usually) deliver the first bytes received for a given window
* UDP assassination (via ICMP) / insertion
* Cryptographic downgrade attacks on HTTPS etc
===Layer 5===
* FireSheep- and BEAST-like session hijacking
* Progressive user identity/demographic discovery aka "maximum creepy" (heuristics on machine name, web pages visited, accounts revealed, mails sent etc)
** Watch for and aggregate probed wireless networks, DHCP lease renewals, etc
* Rogue DNS service
* File-and-signature association for insecure checksums + csums updated-to-order

==Portability==
Omphalos currently only runs or indeed builds on fairly recent Linux systems, due to extensive use of advanced capabilities of the Linux networking stack (and the small fact that I don't run anything else). I doubt that I would accept patches to add Windows/MacOSX support, but you're certainly welcome to maintain them yourself. Once the main functionality set is complete (0.98 release), I'll add support for falling back to plain old PF_PACKET sockets without ringbuffers; that ought add support for any UNIX-based OS with a basic <tt>rtnetlink</tt> implementation.
===User Interfaces===
* <tt>omphalos-tty</tt>: line-based console output with readline-based input
* <tt>omphalos-ncurses</tt>: screen-based terminal output with ncurses-based input
* GTK: I'd like to add a GTK UI, but it's not a major priority
** If you'd like to contribute freely-licensed, original artwork to this effort, please contact me!
* WxWidgets, QT: Dubious that I'll add one, but I'd take patches.
* Java: nope
==Project documentation==
Transcluded from top of my git repository at GitHub.
===README===
<include src="https://raw.github.com/dankamongmen/omphalos/master/README" />

===Data Organization===
<include src="https://raw.github.com/dankamongmen/omphalos/master/doc/dataorganization.txt" />

----
<blockquote>''One of her sisterhood lugged me squealing into life. Creation from nothing. What has she in the bag? A misbirth with a trailing navelcord, hushed in ruddy wool. The cords of all link back, strandentwining cable of all flesh. That is why mystic monks. Will you be as gods? Gaze in your omphalos.'' -- James Joyce, ''[http://www.doc.ic.ac.uk/~rac101/concord/texts/ulysses/files/ulysses3.html Ulysses]''</blockquote>
<hr>
==See Also==
* [[Packet sockets]]

[[CATEGORY: Projects]]
[[CATEGORY: Networking]]
[[CATEGORY: Offensive Computing]]

File:Omphalos.png

2012-05-07T05:31:43Z

Dank: Omphalos: Network Dominance.

Omphalos: Network Dominance.

Omphalos

2012-05-07T05:31:29Z

Dank:

[[File:omphalos.png]]
[[File:omphalos-2011-12-01.jpg|thumb|right|Three omphalos processes, 2011-12-01]]
A tool for network enumeration, protection, observation and domination. Omphalos makes use of passive and active portscanning, DNS/DHCP/[[Zeroconf]] server interrogation, portknock detection, covert channel detection and establishment, ARP scanning, automatic WEP cracking, man-in-the-middling, and a whole host of other tricks. GPS integration? Oh yes. Coordination across multiple interfaces? Of course. Use of Linux's MMAP_RX_SOCKET and MMAP_TX_SOCKET? Wouldn't have it any other way. Userspace networking is made visible to the host via a [[TUN/TAP]] device. While designed as an offensive tool, omphalos has proven useful for network debugging and troubleshooting, as well as experimentation.

'''The latest release is [http://dank.qemfd.net/src/omphalos/rel/current/ 0.99.0 (β)], released 2011-12-01.'''

Omphalos is not a "''point-and-click''" tool so much as "''pull the pin''" or perhaps "''spray the area''". Default behavior is to redirect and seize all traffic, attack weak cryptosystems, archive authentication materials, and learn everything that can be learned. Ideally, a tiny microprocessor would be paired with power and a network device, stealthily physically inserted into a network, and left there; <tt>omphalos</tt> and [[Hackery#liburine|liburine]] would then combine to provide complete network dominance. I hope to combine network programming and high-performance computing to create a tool capable of much havoc.

'''Omphalos: Because one layer is never enough.''' Code is hosted on [https://github.com/dankamongmen/omphalos GitHub]. Bugtracking is hosted on [http://dank.qemfd.net/bugzilla/buglist.cgi?cmdtype=runnamed&namedcmd=omphalos qemfd-bugzilla]. There's a mailing list at [http://groups.google.com/group/omphalos-dev Google Groups].
==Similar Tools==
* [http://www.thoughtcrime.org/software/sslsniff/ SSLSNIFF] from Thoughtcrime Labs
* [http://ettercap.sourceforge.net/ ettercap] by Alberto Ornaghi and Marco Valleri
* [http://www.nixgeneration.com/~jaime/netdiscover/ Netdiscover] by Jaime Peñalba
* [http://www.netresec.com/?page=NetworkMiner NetworkMiner] from NETRESEC AB
* [http://www.jdisc.com/ JDisc Discovery] from JDisc UG
* [http://www.lantopolog.com/ LanTopolog] by Yuriy Volokitin
* [http://code.google.com/p/mirandaupnptool/ Miranda] by Craig Heffner
===Countertools===
We want to defeat systems like:
* [http://arpon.sourceforge.net/ ArpON] by Andrea Di Pasquale et al
===Subsumed Tools===
Omphalos implements all or portions of the functionality of the following tools:
* [[Avahi]], the linux [[zeroconf]] daemon
* [http://www.litech.org/radvd/ radvd], the linux IPv6 Router Advertisement daemon

==Versions/Milestones/Releases==
{| border="1" class="wikitable"
! Version
! Release date
! Features
|-
|0.98 (initial alpha)
|'''[https://github.com/dankamongmen/omphalos/tree/v0.98alpha 2011-10-07]''' (actual)
2011-09-23 (planned)
|
*Detection of network entities at layers 2 and 3.
*Dynamic handling of devices, routes, neighbors and addresses
*Full [[netlink]], ethtool, nl80211 and wireless extensions support
*TTY and [[ncurses]]-based UI's
*[[ARP]]- and [[DNS]]-based probing
|-
|0.99.0β (initial beta)
|'''[https://github.com/dankamongmen/omphalos/tree/v0.99.0β 2011-12-01]''' (actual)
2011-11-11 (planned)
|
*Routing/iptables configuration capabilities
*Hostapd and AP-spoofing support
*Spoofing support at layers 2 and 3
*[[Zeroconf]]- and WINS-based probing
|-
|1.0
|2011-12-25 (planned)
|
*Automated selection and execution of previous capabilities
*GPS support
*Logging support
*[[Topology Discovery|LLTD]] and some [[NetBIOS]] support
|}

==General Features==
Some planned, some implemented...
* Modes of operation governing automatic behavior, from "Silent" to "Hostile":
{| border="1" class="wikitable"
! Mode
! Summary
! Operating characteristics
|-
| Silent
| Take no actions, only watch.
|
* TX ringbuffers/sockets are not automatically created
* No packets will be issued by omphalos unless requested
* No automatic modifications to host networking state
|-
| Stealthy
| Take only the actions of a normally-configured host.
|
* [[ARP]] queries will be automatically issued
* [[DNS]] and [[Zeroconf]] queries will be issued, but only as the host is configured
* No automatic modifications to host networking state
|-
| Active
| Learn what we can, possibly standing out from the crowd.
|
* Make free use of detected information for further recon
* No automatic modifications to host networking state
|-
| Aggressive
| Learn things quickly, in ways that will be noticed.
|
* "Active", plus...
* Periodic and triggered wide-spectrum active scanning
* Omphalos will freely manipulate host networking state
|-
| Forceful
| Actively disrupt the network, rerouting traffic through us.
|
* Continuous scanning of the network
* MitM automatically effected wherever possible
* DoS will be employed to make MitM more effective
* Omphalos will freely manipulate host networking state
|-
| Hostile
| Attempt to make the network unusable.
|
* Same as "Forceful", but don't pass traffic along once MitM'd.
* Actively employ null routing.
* DoS employed upon network infrastructure, carrier, and and egress.
|-
|}
* GPS coordination and tagging
* Fully dynamic behavior viz the networking stack. Add and remove cards, routes, addresses...
* Audiovisual plugins ('''FIXME''' detail! lots of good ideas here)
* Event/scripting engine
** Fine-grained MitM packet manipulation, filtering and generation via [[Hackery#parvenu|Parvenu]] and domain-specific languages
** Fine-grained, one-click identity theft at any desired layer(s) (assumption of MAC, IP, cookies, etc)
*** Eat your heart out, [http://codebutler.com/firesheep Firesheep]!
* Full integration with [[Linux_APIs#POSIX_capabilities|POSIX capabilities]] for fine-grained security (nothing runs as the superuser)
* Covert channel detection at all layers via [[Hackery#Zetetic|Zetetic]]
* Opportunistic, secure remote control via [[Hackery#liburine|liburine]]
===Network Analysis===
* Network analysis and debugging ought be spun out into [[Hackery#drbenway|Dr. Benway]]
{| class="wikitable" border="1"
! Layer
! Subdivisions
! What's tracked
! Notes
|-
| Layer 2
| From both packets and netlink:
* VLANs
* ESSs
|
* Nodes from packets:
** All source hardware addresses seen in packets
** All destination hardware multicast addresses
* Nodes from netlink:
** All hardware addresses in the kernel neighbor cache
** Our hardware addresses
** Hardware broadcast addresses
|
* Node allocation is backed by a mainly-static [[VLHU]]
** At the point an attacker can overwhelm our VLHU, there's effectively nothing on the network but junk packets.
* If something's a source, it's being claimed as present here on the network. A destination means nothing, except in the case of multicast.
* Someone else sending with our MAC address ought be noted, unless we stole their MAC address
* We can't generally differentiate between two other physical hosts using the same MAC
** Multiple interfaces might actually be sharing a MAC intentionally for low-latency failover
** Upshot: we don't/can't care. We only care if someone else uses *our* MAC (unless told it's ok).
* We can't detect a spoofed MAC, but we can send our own ARP probes and at least determine whether the MAC's being serviced
|-
| Layer 3
| From both packets and netlink:
* Networks
|
We don't want to track network addresses beyond our broadcast domain. That's difficult to determine, however, without a working routing configuration (ie, an address). We'll thus assume that RFC1918 membership or service of an L2-restricted service (like [[DHCP]] or [[Zeroconf]]) indicates local presence (if it doesn't, it indicates misconfiguration). This means that
* Hosts from netlink:
** All network addresses in the kernel neighbor cache
** Configured router addresses
** Our configured network addresses
** Configured broadcast addresses
* Hosts from packets:
** All source network addresses from the RFC1918 networks
** All source network addresses to which we have a configured route
** All source network addresses observed offering L2-restricted services
*** All routers and nameservers named in a DHCP packet
** All destination network multicast addresses
|
* Host allocation is backed by a dynamic [[VLHU]].
* More dynamic and larger VLHU than that for layer 2, since we can have more hosts than nodes -- imagine a /0 route configuration sitting on an internet backbone. Small implementations of ARP tables and CAMs in nodes/switches means, say, 4k nodes ought almost always be sufficient for any interface.
* Multiple nodes can share a host address, but it can also indicate a problem
* Other nodes using *our* host addresses is a problem unless told otherwise
* Seeing an L3 address on a MAC means either:
** There's another network present locally (if we have no route to the L3, and the MAC responds to an [[ARP]] query for the L3), or
** That MAC is routing to that address (if the MAC is associated with a route to the L3), or
** That MAC serves that address (if we have a local route to the address)
*** Perhaps only temporarily, and perhaps without service provision (eg DHCP requests), or
** There's any variety of misconfiguration/failure/adversary at work (le sigh)
* Upshot: we can discover the local network(s) without relying on any configuration, even those which don't advertise (ie with [[DHCP]])
|-
| Layer 4
|
| From packets:
* DNS and DHCP servers
| We don't use the local configuration because there's no unified API to access it, nor track changes to it. We'll detect DNS quickly enough if anything's actually using the network, and can partially detect host DNS servers simply by kicking off a query through the standard resolver library (even if we don't use the provided result).
|-
|}

==Analysis and Attack Capabilities==
===Physical Layer Support===
{| class="wikitable" border="1"
! Protocol
! [[Standards|Standard]]
! [[Pcap|libpcap]] linktype
! Linux ARP type
! Analyzed?
|-
| BSD Loopback
| ?
| DLT_NULL
| N/A
| No
|-
| Linux Cooked Capture
| [http://linuxmanpages.com/man7/packet.7.php packet(7)]
| DLT_LINUX_SLL
| N/A
| Yes
|-
| [[Ethernet]]
* Ethernet II/DIX
* Novell 802.3
* IEEE 802.2 LLC
* SNAP
* 802.1Q VLAN/802.1p QoS (IEEE 802.3ac)
| IEEE 802.3-2008
| DLT_EN10MB
| ARPHRD_ETHER
| Yes
|-
| Token Ring
| IEEE 802.5
| DLT_IEEE802
| ARPHRD_IEEE802_TR
| No
|-
| ARCNET
| ANSI 878.1
|
* DLT_ARCNET
* DLT_ARCNET_LINUX
| ARPHRD_ARCNET
| No
|-
| SLIP
(Serial Line Internet Protocol)
|
* RFC 1055 (SLIP)
* RFC 1154 (CSLIP)
| DLT_SLIP
|
* ARPHRD_SLIP
* ARPHRD_SLIP6
* ARPHRD_CSLIP
* ARPHRD_CSLIP6
| No
|-
| PPP (Point-to-Point Protocol)
* BSD/OS PPP
* PPP over serial
* PPPoE (PPP over [[Ethernet]])
* PPPoA (PPP over ATM)
* Cisco PPP/HDLC
| RFC 1661
* ?
* RFC 1662
* RFC 2516
* RFC 2364
* RFC 1547
| DLT_PPP
* DLT_PPP_BSDOS
* DLT_PPP_SERIAL
* DLT_PPP_ETHER
* ?
* DLT_C_HDLC
| ARPHRD_PPP
| Partial
* No
* No
* No
* No
* Yes
|-
| FDDI
(Fiber Distributed Data Interface)
|
* MAC: ANSI X3.139-1987 / ISO 9314-2
* PHY: ANSI X3.148-1988 / ISO 9314-1
| DLT_FDDI
| ARPHRD_FDDI
| No
|-
| Fibre Channel
| RFC 2625
| DLT_IP_OVER_FC
|
* ARPHRD_FCPP
* ARPHRD_FCAL
* ARPHRD_FCPL
* ARPHRD_FCFABRIC
| No
|-
| IrDA
(Infrared Data Association)
|
* IrDA PHY Spec v1.5
* IrDA Link Access Protocol v1.1
| DLT_LINUX_IRDA
| ARPHRD_IRDA
| Yes
|-
| Radiotap
| De facto
| DLT_IEEE802_11_RADIO
| ARPHRD_IEEE80211_RADIOTAP
| Yes
|-
| Firewire
| IEEE 1394
| N/A
| ARPHRD_IEEE1394
| Yes
|-
| Frame Relay
| ?
| DLT_FRELAY
| ARPHRD_FRAD
| No
|-
| Apple LocalTalk
| ?
| DLT_LTALK
| ARPHRD_APPLETLK
| No
|-
| LAPD
(Link Access Protocol - D Channel)
| ITU Q.921
| DLT_LINUX_LAPD
| ARPHRD_LAPB
| No
|-
|}

===Layer 2===
====Topology Discovery====
''For more information, see the [[Topology Discovery]] page.''
{| class="wikitable" border="1"
|-
! Protocol
! Standard
! Support
|-
| [[Topology_Discovery#Link-Local_Topology_Discovery_.28LLTD.29_Protocol|LLTDP]]
| Microsoft
|
* Extraction of data from HELLO packets
* Enumeration via DISCOVERY requests
|-
| [[Topology_Discovery#Link-Layer_Discovery_Protocol_.28LLDP.29|LLDP]]
| IEEE 802.1AB-2005
|
* None yet
|-
| [[Topology_Discovery#Cisco_Discovery_Protocol_.28CDP.29|CDP]]
| Cisco
|
* None yet
|-
| STP
| IEEE 802.1D
|
* Minimal analysis of BDPUs
|-
|}
====802.3/Ethernet II====
* Detect physical hosts on the network via MAC analysis
** Classify as locally-generated, multicast, etc
* Flood a network with spoofed MAC addresses, in the hope of forcing fail-open behavior to facilitate attacks (see <tt>macof</tt> from [http://monkey.org/~dugsong/dsniff/ dsniff] and ''Hacking Layer 2: Fun with Ethernet Switches'' from BlackHat 2002)
* Probe and autodetect CAM sizes and hash functions, allowing for minimal CAM overflows
* Autodetect host [[ARP]] timings and replacement policies, allowing for stealthy man-in-the-middling
* Reverse and direct man-in-the-middling (answer all queries for an address, from an address, or both)
* Gratuitous ARP ("enclosure")
* Controlled SNAT of outgoing traffic at layer 2, to create multiple realistic hosts ("Capgras delusions")
* Automated [[ARP]] jamming and man-in-the-middling
* [http://en.wikipedia.org/wiki/Arpwatch Arpwatch-like] layer 2 monitoring
* VLAN hopping

====802.11====
* Passively attack weak cryptosystems (especially WEP), or do so actively if configured
* Channel hopping or locked operation
* Spectrum and noise analysis plugin
* Respond as master to probed networks, on a to-order basis
* Ability to run omphalos in as an AP client via userspace networking atop radiotap (Monitor mode) and WPA/EAPOL support
** Or, more likely, some kind of hostapd control using Master mode
* "[http://www.airtightnetworks.com/WPA2-Hole196 Hole 196]" injection
* Viehbock's [http://sviehb.files.wordpress.com/2011/12/viehboeck_wps.pdf WPS EAP-NACK] brute-force attack ([http://www.kb.cert.org/vuls/id/723755 US-CERT #723755])

===Layer 3===
* ICMP redirects
** We're closer than the remote server; jam ours in, and let the real one be tossed as duplicate
* A whole world of IPv6 mischief
* Rogue DHCP service
* SNAT for routing enbondaged neighbors
* ...much more

===Layer 4===
* TCP assassination (via RST) / arbitrary corruption
** Most [[TCP]] implementations will (usually) deliver the first bytes received for a given window
* UDP assassination (via ICMP) / insertion
* Cryptographic downgrade attacks on HTTPS etc
===Layer 5===
* FireSheep- and BEAST-like session hijacking
* Progressive user identity/demographic discovery aka "maximum creepy" (heuristics on machine name, web pages visited, accounts revealed, mails sent etc)
** Watch for and aggregate probed wireless networks, DHCP lease renewals, etc
* Rogue DNS service
* File-and-signature association for insecure checksums + csums updated-to-order

==Portability==
Omphalos currently only runs or indeed builds on fairly recent Linux systems, due to extensive use of advanced capabilities of the Linux networking stack (and the small fact that I don't run anything else). I doubt that I would accept patches to add Windows/MacOSX support, but you're certainly welcome to maintain them yourself. Once the main functionality set is complete (0.98 release), I'll add support for falling back to plain old PF_PACKET sockets without ringbuffers; that ought add support for any UNIX-based OS with a basic <tt>rtnetlink</tt> implementation.
===User Interfaces===
* <tt>omphalos-tty</tt>: line-based console output with readline-based input
* <tt>omphalos-ncurses</tt>: screen-based terminal output with ncurses-based input
* GTK: I'd like to add a GTK UI, but it's not a major priority
** If you'd like to contribute freely-licensed, original artwork to this effort, please contact me!
* WxWidgets, QT: Dubious that I'll add one, but I'd take patches.
* Java: nope
==Project documentation==
Transcluded from top of my git repository at GitHub.
===README===
<include src="https://raw.github.com/dankamongmen/omphalos/master/README" />

===Data Organization===
<include src="https://raw.github.com/dankamongmen/omphalos/master/doc/dataorganization.txt" />

----
<blockquote>''One of her sisterhood lugged me squealing into life. Creation from nothing. What has she in the bag? A misbirth with a trailing navelcord, hushed in ruddy wool. The cords of all link back, strandentwining cable of all flesh. That is why mystic monks. Will you be as gods? Gaze in your omphalos.'' -- James Joyce, ''[http://www.doc.ic.ac.uk/~rac101/concord/texts/ulysses/files/ulysses3.html Ulysses]''</blockquote>
<hr>
==See Also==
* [[Packet sockets]]

[[CATEGORY: Projects]]
[[CATEGORY: Networking]]
[[CATEGORY: Offensive Computing]]

Solomonoff-Levin distribution

2012-05-04T11:00:22Z

Dank: Created page with "Category: Computer Science Eponyms"

[[Category: Computer Science Eponyms]]

Cranfield method

2012-05-04T10:31:37Z

Dank: Created page with "A methodology for minimizing Boolean functions. Category: Computer Science Eponyms"

A methodology for minimizing Boolean functions.

[[Category: Computer Science Eponyms]]

Zobrist hashing

2012-05-04T10:25:20Z

Dank: Created page with "Category: Computer Science Eponyms"

[[Category: Computer Science Eponyms]]

Libdank

2012-05-01T05:25:01Z

Dank:

<blockquote>A Real Programmer keeps his code locked up in a card file, because it implies that its owner cannot leave his important programs unguarded. --[http://www.pbm.com/~lindahl/real.programmers.html Real Programmer's Don't Use Pascal]</blockquote>
<blockquote>Why do programmers reinvent wheels? There are many reasons, reaching all the way from the narrowly technical to the psychology of programmers and the economics of the software production system. The damage from the endemic waste of programming time reaches all these levels as well. --[http://www.faqs.org/docs/artu/ch16s01.html The Art of UNIX Programming]</blockquote>
As innumerably many programming books report (I myself have no idea where I first read it), experienced programmers tend to carry with them a sizable selection of utility code they've built up over the years -- those general-use routines which just missed inclusion in the [[libc|standard libraries]] but don't justify an [[interesting libraries|external library]] by themselves. I too am guilty of a hubristic, eponymous extension to the [[ISO C99|C language]] -- libdank.

==Resources==
* [https://github.com/dankamongmen/libdank/ git] on GitHub
* [http://www.bugzilla.org/ bugzilla], hosted here on http://dank.qemfd.net/bugzilla/
===Milestones===
[[Category: Projects]]

blackwiki:Community Portal

2012-04-29T17:14:11Z

Dank: /* blackwiki news */

There's pages about [http://dank.qemfd.net/dankwiki/index.php/blackwiki:About blackwiki] and [[User:Dank|myself]].

I now offer consulting services through [http://www.sprezzaturacomputing.com sprezzatech] (a division of Sprezzatura Computing).
----
==blackwiki news==
* Upgraded from MediaWiki 1.18.1 to 1.18.3, moving from [[subversion]] to [[git]] as we did so [[User:Dank|Dank]] 17:14, 29 April 2012 (UTC)
* I have acquired an SSL certificate for dank.qemfd.net. Use it! https://dank.qemfd.net/dankwiki/index.php/Hack_on
* Upgraded to 1.18. A few things seem broken (why are we back on MonoBook?); fixing them up... [[User:Dank|Dank]] 19:56, 28 November 2011 (CST)
* Moved from the MonoBook to MediaWiki 1.17's new Vector skin. Very pretty! [[User:Dank|Dank]] 10:15, 22 November 2011 (CST)
* Apparently [http://www.mediawiki.org/wiki/Memcached memcached] support changed, and I didn't realize it. I've updated using the documentation at [http://www.mediawiki.org/wiki/Manual:$wgMainCacheType MediaWiki's cache page].
** Things ought be served noticeably faster now, hopefully. [[User:Dank|Dank]] 11:30, 1 October 2011 (CDT)
* Moved gplus, facebook and donation buttons from footer to sidebar. Pimp me, vigilant readers! [[User:Dank|Dank]] 23:08, 26 September 2011 (CDT)
* Fixed SphinxSearch and RSS [[User:Dank|Dank]] 07:00, 21 September 2011 (CDT)
* Upgraded to [[Special:Version|1.17.0]] [[User:Dank|Dank]] 15:49, 31 July 2011 (EDT)
* I have upgraded us from 1.15.1 to 1.16.5. Things look good. On to 1.17 in a few hours! [[User:Dank|Dank]] 18:26, 23 July 2011 (EDT)
** SphinxSearch is working again (see [http://dank.qemfd.net/bugzilla/show_bug.cgi?id=242 bug 242]), and upgraded to 2.0.2-dev-r2894
* I need [http://dank.qemfd.net/bugzilla/show_bug.cgi?id=242 update] this [http://dank.qemfd.net/bugzilla/show_bug.cgi?id=243 bitch] across two MediaWiki versions
** We'll be going from 1.15.1 to 1.17 very soon -- [[User:Dank|Dank]] 09:36, 19 July 2011 (UTC)
* fixed [http://www.mediawiki.org/wiki/Extension:Bugzilla_Reports BuzillaReports] for [[libtorque]] and [[omphalos]] - [[User:Dank|Dank]] 15:17, 6 July 2011 (UTC)
* I fixed Email::Simple's install, eliminating some bugzilla failures - [[User:Dank|Dank]] 03:24, 26 June 2011 (UTC)
* '''EXCITING NEWS!!!''' Blackwiki has moved from 1and1.com to Linode.
** Our connectivity is ''much'' better, as is the whole setup. '''Could this be the end of prolonged downtime?'''
** We're now running [[Debian|Debian Squeeze]] rather than some ghetto Ubuntu
** Look for an upgrade to MediaWiki 1.16.x soon!
* I fixed the [[Special:RecentChanges|Recent Changes]] page, which I fucked up during the 1.15.1 upgrade
** Needed to run update.php -- [http://www.mwusers.com/forums/showthread.php?11694-1.15.1-SQL-Error-on-recent-changes-page see this forum]. Stupid me!
* I've killed the cacti link as of 2011-05-14, because I fucked up cacti
* If you'd like to help fund blackwiki for some reason, please click on the "Donate" button on the footer of any blackwiki page.
* I've added Google AdSense as of 2010-07-24. Let's try this, players!

Debian

2012-04-29T17:13:24Z

Dank:

[[Image:Debianelitism.jpg|right|thumb|Would you like some fries with that elitism?]]

It's the bees' knees. It's the wasps' nipples.
* Things I do to a new [[Debian Unstable|Unstable (sid) box]]
* [[Packages by Purpose]]
* My resolution this year is to file bugs in the [http://www.debian.org/Bugs/Reporting DBTS] more quickly and more often. Well, it isn't really, but I ought do so. Bugs filed thus far, and their resolutions:
** [http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=469601 #469601], '''nut-hal-drivers''' locks up on post-install
** [http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=469937 #469937], '''statsvn''' has problems with filenames containing spaces (''fixed upstream'', ''resolved'')
** [http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=471111 #471111], '''mpd''' isn't shut down properly
** [http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=509499 #509499], '''strace''' doesn't match [[Linux APIs|sendfile(2)]] properly (''provided patch'', ''resolved'')
** [http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=530154 #530154], '''bugz''' doesn't provide a man page
** [http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=533360 #533360], '''[[glibc|libc6]]''' 2.9-15 broke [[Linux APIs|signalfd]] creation with SFD_* flags (''resolved'')
** [http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=533362 #533362], '''ia32-libs''' uninstallable against [[glibc|libc6]] 2.9-15 (''resolved'')
** [http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=552260 #552260], '''kernel-package''' with <tt>install_vmlinux</tt> set + grub2 == unbootable entries
** [http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=553298 #553298], '''libcpuset''' drops core if an empty [[Cpuset|cgroup/cpuset]] fs is mounted
** [http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=554901 #554901], '''[[glibc|eglibc]]''' is missing const casts in CPU_ISSET() (''provided patch'', ''resolved'')
* I'd also like to become a [https://nm.debian.org/nmlist.php Debian Developer]. ITP ideas:
** the [[SSHFP|sshfp]] program, maintained by [http://www.xelerance.com/software/sshfp/ Xelerance]
** Florian Amrhein's [http://amrhein.eu/newsportal/ newsportal] NNTP-to-HTTP gateway
** Rice University's [http://hpctoolkit.org/ HPCToolkit]
** HP+MIT's [http://groups.csail.mit.edu/cag/dynamorio/ DynamoRIO]
** [[Omphalos]]
** Pick up orphaned OProfile
[[CATEGORY: Linux]]

ZFS

2012-04-28T15:42:10Z

Dank: /* Debian-installer */

Screenshots from [http://www.sprezzatech.com/sprezzos.html SprezzOS] prereleases.
==[[Growlight|installer]]==
http://dank.qemfd.net/tabpower/d-i-zfs.png

ZFS

2012-04-28T15:41:51Z

Dank:

Screenshots from [http://www.sprezzatech.com/sprezzos.html SprezzOS] prereleases.
==[[Debian-installer]]==
http://dank.qemfd.net/tabpower/d-i-zfs.png

ZFS

2012-04-28T15:41:32Z

Dank:

Screenshots from [http://www.sprezzatech.com/sprezzos.html SprezzOS] prereleases.
http://dank.qemfd.net/tabpower/d-i-zfs.png

ZFS

2012-04-28T06:55:39Z

Dank: Created page with "http://dank.qemfd.net/tabpower/d-i-zfs.png"

http://dank.qemfd.net/tabpower/d-i-zfs.png

Bookshelves

2012-04-27T20:08:08Z

Dank: /* Alexandria 2010 */

[[Image:Ivegotyourhackerjeopardyquestionsrighthere.jpeg|thumb|alt="I've got your hacker jeopardy answers right here"|The Wall of Rigor!]]
I am in desperate need of bookshelves ('''update: [[Bookshelves#Alexandria_2010|not anymore]]!'''). Desirable traits include:
* Ash/matted black wood (but not steel, at least not any steel cases I've seen)!
* 72 inches high or more. 76- and 80-inch shelves aren't rare by any means but do narrow things down quite a bit
* Either no doors, or the ability to easily remove them without disfiguring or damaging the case
* As rectilinear a form as possible, and little wasting of space by moulding, thick sides, etc
* Solid top

Some nice ones:
* Hayden Tall 30": http://www.crateandbarrel.com/family.aspx?c=1090&f=27098 $600
* Tuscan Center (85 3/4"H x 46 1/2"W x 18 3/4"D) http://www.ballarddesigns.com/Furniture/Bookcases/Tuscan-Center-Bookcase/p/2243 $799
* Riverside Summit 84 (30W x 11.5D x 84H) http://www.bookcasesgalore.com/bookcases/standard/riversidesummit84inchbookcase.cfm $429
==Too many books, too few bookshelves==
<gallery>
File:southernbooks.png|Southern Wall at 689 Myrtle
File:northernbooks.png|Northern Wall at 689 Myrtle
File:shelfofrigor.png|Shelf of Rigor at 689 Myrtle
</gallery>
==Alexandria 2010==
I've finally constructed suitable shelving here at [[Viewpoint]]!
<gallery>
File:bay1phase2.jpg|Bay 1, Phase 1
File:bay1phase3.jpg|Bay 1, Phase 2
File:bay1phase4.jpg|Bay 1, Phase 3
</gallery>
<gallery>
File:IMG_0240.JPG|Bay 2
File:bay2.jpg|Bay 2, closeup
</gallery>
===Filing system===
* Biographies ought not be separated out into their own section, but rather included among the appropriate subjects.
* Fiction is separated into collections, poetics, dialogues, and long prose
** Collections are extracted largely due to shelving concerns

File:Bay2.jpg

2012-04-27T20:07:08Z

Dank: Bay 2, closeup

Bay 2, closeup

File:IMG 0240.JPG

2012-04-27T20:04:55Z

Dank: Bay 2

Bay 2

File:Machines-ToC.pdf

2012-04-26T14:15:19Z

Dank: uploaded a new version of "File:Machines-ToC.pdf"

Table of Contents for my upcoming book, ''[[Book_ideas#The_Finest_Machine|The Finest Machine]]''.

Book ideas

2012-04-26T14:09:41Z

Dank: /* The Finest Machine */

==The Finest Machine==
[[File:Kickstarter.png|thumb|right|Funded (possibly) on Kickstarter]]
''The Finest Machine: The Science and the Joy of Computing''.
* Computing from the ground up, beginning with formal systems and moving up through information theory, VLSI, [[Architecture|microprocessors]] and [[Programming Language Theory|programming languages]].
* [http://www.kickstarter.com/projects/nickblack/the-finest-machine Kickstarter project]
* [[media:Machines-ToC.pdf|Table of Contents]]

==Nascent Nonfiction==
* Fill in [[:Category:Computer_Science_Eponyms|computer science eponym list]], market as a phatty ''Dictionary of Ideas'' or ''Binet's Reader's Encyclopedia''-like deal
* (major and semi-esoteric) [[Trees]]. A chapter on each, kinda like ''The Periodic Kingdom''
* A guide to low-latency, high-throughput I/O on UNIX and Windows, with an emphasis on API's
* [[CS GRE|Computer Science GRE]] exam prep
* Definitive biography of von Neumann (as of 2009, the three major ones are all garbage)
** possible title: ''Fekete Pestis'' (sets up unfortunate puns on my last name, though)
* '''The Well-Tempered Computer''' (working title): an in-depth guide to modern computer hardware with an emphasis on standards
** Everything from the input power to the output LEDs
** Creative Commons license

==Nascent Fiction==
* ''Maximum Scrunch'', a novel
** the title comes from Hans Bethe's ''Road from Los Alamos'', referring to the conditions at which implosion turns to explosion in a supernova's core collapse

Book ideas

2012-04-26T14:09:10Z

Dank: move TFM to the top

==The Finest Machine==
[[File:Kickstarter.png|thumb|right|Funded (possibly) on Kickstarter]]
''The Finest Machine: The Science and the Joy of Computing''.
* Computing from the ground up, beginning with formal systems and moving up through information theory, VLSI, microprocessors and programming languages.
* [http://www.kickstarter.com/projects/nickblack/the-finest-machine Kickstarter project]
* [[media:Machines-ToC.pdf|Table of Contents]]

==Nascent Nonfiction==
* Fill in [[:Category:Computer_Science_Eponyms|computer science eponym list]], market as a phatty ''Dictionary of Ideas'' or ''Binet's Reader's Encyclopedia''-like deal
* (major and semi-esoteric) [[Trees]]. A chapter on each, kinda like ''The Periodic Kingdom''
* A guide to low-latency, high-throughput I/O on UNIX and Windows, with an emphasis on API's
* [[CS GRE|Computer Science GRE]] exam prep
* Definitive biography of von Neumann (as of 2009, the three major ones are all garbage)
** possible title: ''Fekete Pestis'' (sets up unfortunate puns on my last name, though)
* '''The Well-Tempered Computer''' (working title): an in-depth guide to modern computer hardware with an emphasis on standards
** Everything from the input power to the output LEDs
** Creative Commons license

==Nascent Fiction==
* ''Maximum Scrunch'', a novel
** the title comes from Hans Bethe's ''Road from Los Alamos'', referring to the conditions at which implosion turns to explosion in a supernova's core collapse

2012-04-15T17:13:18Z

Dank: /* Custom kernel */

I've been modifying the [[Debian]] installer for the first release of [http://www.sprezzos.com SprezzOS]. It's been quite the PITA.
==Build environment==
* debootstrap --variant buildd http://ftp.us.debian.org unstable
* apt-get source debian-installer

==Custom kernel==
* apt-get source linux-2.6
** apt-get install linux-source-3.2 gets you a /usr/src tarball with no debian/ subdirectory
** apt-get install linux-source gets you something called 'linux_latest' (investigate!)
* cd linux-2.6-3.2.14 or whatever
* dpkg-buildpackage -j8
output includes a full set of udebs:
<pre>root@skynet:/linux-2.6-3.2.14# ls ../*udeb
../acpi-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../ata-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../btrfs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../cdrom-core-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../core-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../crc-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../crypto-dm-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../crypto-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../efi-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../event-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../ext2-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../ext3-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../ext4-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../fat-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../fb-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../firewire-core-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../floppy-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../i2c-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../input-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../irda-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../isofs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../jfs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../kernel-image-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../loop-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../md-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../mmc-core-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../mmc-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../mouse-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../multipath-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../nbd-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../nic-extra-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../nic-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../nic-pcmcia-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../nic-shared-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../nic-usb-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../nic-wireless-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../ntfs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../parport-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../pata-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../pcmcia-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../pcmcia-storage-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../plip-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../ppp-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../qnx4-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../reiserfs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../sata-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../scsi-common-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../scsi-core-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../scsi-extra-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../scsi-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../serial-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../sound-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../speakup-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../squashfs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../ufs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../uinput-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../usb-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../usb-serial-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../usb-storage-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../virtio-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../xfs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../zlib-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
root@skynet:/linux-2.6-3.2.14# </pre>
* cp *udeb DIROOT/build/localudebs
* add their names to new file DIROOT/build/pkg-lists/local
* add <tt>deb copy:/DIROOT/build/ localudebs/</tt> to DIROOT/build/sources.list.udeb.local

Debian installer

2012-04-15T17:09:03Z

Dank:

I've been modifying the [[Debian]] installer for the first release of [http://www.sprezzos.com SprezzOS]. It's been quite the PITA.
==Build environment==
* debootstrap --variant buildd http://ftp.us.debian.org unstable
* apt-get source debian-installer

==Custom kernel==
* apt-get source linux-2.6
** apt-get install linux-source-3.2 gets you a /usr/src tarball with no debian/ subdirectory
** apt-get install linux-source gets you something called 'linux_latest' (investigate!)
* cd linux-2.6-3.2.14 or whatever
* dpkg-buildpackage -j8
output includes a full set of udebs:
<pre>root@skynet:/linux-2.6-3.2.14# ls ../*udeb
../acpi-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../ata-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../btrfs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../cdrom-core-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../core-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../crc-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../crypto-dm-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../crypto-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../efi-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../event-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../ext2-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../ext3-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../ext4-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../fat-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../fb-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../firewire-core-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../floppy-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../i2c-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../input-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../irda-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../isofs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../jfs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../kernel-image-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../loop-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../md-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../mmc-core-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../mmc-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../mouse-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../multipath-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../nbd-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../nic-extra-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../nic-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../nic-pcmcia-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../nic-shared-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../nic-usb-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../nic-wireless-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../ntfs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../parport-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../pata-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../pcmcia-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../pcmcia-storage-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../plip-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../ppp-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../qnx4-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../reiserfs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../sata-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../scsi-common-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../scsi-core-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../scsi-extra-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../scsi-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../serial-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../sound-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../speakup-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../squashfs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../ufs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../uinput-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../usb-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../usb-serial-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../usb-storage-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../virtio-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../xfs-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
../zlib-modules-3.2.0-2-amd64-di_3.2.14-1_amd64.udeb
root@skynet:/linux-2.6-3.2.14# </pre>
* cp *udeb DIROOT/build/localudebs
* add their names to new file DIROOT/build/pkg-lists/local