Andrew Cooke | Contents | Latest | RSS | Twitter | Previous | Next

C[omp]ute

Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

Personal Projects

Lepl parser for Python.

Colorless Green.

Photography around Santiago.

SVG experiment.

Professional Portfolio

Calibration of seismometers.

Data access via web services.

Cache rewrite.

Extending OpenSSH.

C-ORM: docs, API.

Last 100 entries

Removing Lowers; Mnesiacs; [Maths, Link] Dividing By Zero; [Book, Review] Ray Monk - Ludwig Wittgenstein: The Duty Of Genius; [Link, Bike, Computing] Evolving Lacing Patterns; [Jam] Strawberry and Orange Jam; [Chile, Privacy] Biometric Check During Mail Delivery; [Link, Chile, Spanish] Article on the Chilean Drought; [Bike] Extended Gear Ratios, Shimano XT M8000 (24/36 Chainring); Get Coffee Quotes for Cat Soft LLC; [Link, Politics, USA] The Future Of American Democracy; Mass Hysteria; [Review, Books, Links] Kazuo Ishiguro - Never Let Me Go; [Link, Books] David Mitchell's Favourite Japanese Fiction; [Link, Bike] Rear Suspension Geometry; [Link, Cycling, Art] Strava Artwork; [Link, Computing] Useful gcc flags; [Link] Voynich Manuscript Decoded; [Bike] Notes on Servicing Suspension Forks; [Links, Computing] Snap, Flatpack, Appimage; [Link, Computing] Oracle is leaving Java (to die); [Link, Politics] Cubans + Ultrasonics; [Book, Link] Laurent Binet; VirtualBox; [Book, Link] No One's Ways; [Link] The Biggest Problem For Cyclists Is Bad Driving; [Computing] Doxygen, Sphinx, Breathe; [Admin] Brokw Recent Permalinks; [Bike, Chile] Buying Bearings in Santiago; [Computing, Opensuse] Upgrading to 42.3; [Link, Physics] First Support for a Physics Theory of Life; [Link, Bike] Peruvian Frame Maker; [Link] Awesome Game Theory Tit-For-Tat Thing; [Food, Review] La Fabbrica - Good Italian Food In Santiago; [Link, Programming] MySQL UTF8 Broken; [Link, Books] Latin American Authors; [Link, Computing] Optimizatin Puzzle; [Link, Books, Politics] Orwell Prize; [Link] What the Hell Is Happening With Qatar?; [Link] Deep Learning + Virtual Tensor Machines; [Link] Scaled Composites: Largest Wingspan Ever; [Link] SCP Foundation; [Bike] Lessons From 2 Leading 2 Trailing; [Link] Veg Restaurants in Santiago; [Link] List of Contemporary Latin American Authors; [Bike] FTHR; [Link] Whoa - NSA Reduces Collection (of US Residents); [Link] Red Bull's Breitbart; [Link] Linux Threads; [Link] Punycode; [Link] Bull / Girl Statues on Wall Street; [Link] Beautiful Chair Video; Update: Lower Pressures; [Link] Neat Python Exceptions; [Link] Fix for Windows 10 to Avoid Ads; [Link] Attacks on ZRTP; [Link] UK Jazz Invasion; [Review] Cuba; [Link] Aricle on Gender Reversal of US Presidential Debate; {OpenSuse] Fix for Network Offline in Updater Applet; [Link] Parkinson's Related to Gut Flora; Farellones Bike Park; [Meta] Tags; Update: Second Ride; Schwalbe Thunder Burt 2.1 v Continental X-King 2.4; Mountain Biking in Santiago; Books on Ethics; Security Fail from Command Driven Interface; Everything Old is New Again; Interesting Take on Trump's Lies; Chutney v6; References on Entropy; Amusing "Alexa.." broadcast; The Shame of Chile's Education System; Playing mp4 gifs in Firefox on Opensuses Leap 42.2; Concurrency at Microsoft; Globalisation: Uk -> Chile; OpenSuse 42.2 and Synaptics Touch-Pads; Even; Cherry Jam; Lebanese Writer Amin Maalouf; C++ - it's the language of the future; Learning From Trump; Chinese Writer Hu Fayun; And; Apricot Jam; Also; Excellent Article on USA Politics; Oh Metafilter; Prejudice Against The Rurals; Also, Zizek; Trump; Why Trump Won; Doxygen + Latex on CentOS 6; SMASH - Solve 5 Biggest Problems in Physics; Good article on racism, brexit, and social divides; Grandaddy are back!; Consciousness From Max Entropy; Democrats; Harvard Will Fix Black Poverty; Modelling Bicycle Wheels

© 2006-2017 Andrew Cooke (site) / post authors (content).

Some Initial Results for Overlapping Tiles with CUDA

From: "andrew cooke" <andrew@...>

Date: Mon, 28 Jul 2008 20:36:24 -0400 (CLT)

I wrote the following code to simulate (perhaps not exactly) the memory
loads that would occur using CUDA if the data were processed using a
tiling that overlaps (so something like the Matrix example, but with
leaking across the boundaries of the box - perhaps for convolving with a
kernel, for example, or, as in my case, calculating "life").

Using the approach shown in the code (large integer types and a single
overlap) is inefficient because (at least for CUDA 1.0 ad 1.1) the reads
cannot be coalesced - either the half weft is the wrong width, or the
shift (which is less than the half-weft to allow for overlapping) is
wrong.

I'm going to see now if using a smaller integer type and overlapping a
whole half-weft makes more sense (sounds crazy, but might work...).

Andrew


(these is just the core block to give some idea of what's happening)

// run through each tile position
int count = 0;
for (int j = 0; j < nY; j++) {
    for (int i = 0; i < nX; i++) {
        // for each tile, run through the half-warps
        for (int k = 0; k < nHalfWarps; k++) {
            for (int l = 0; l < halfWarp; l++) {
                int localOffset = k * halfWarpWidth + l * word;
                int localX = localOffset % windowX;
                int localY = localOffset / windowX;
                int globalX = i * strideX + localX;
                int globalY = j * strideY + localY;
                int globalOffset = globalY * (*paddedX) + globalX;
                int segStart = globalOffset / segment;
                int segEnd =                                        \
                    (globalOffset + halfWarpWidth - word) / segment;

                if (prop.minor < 2) {
                    // 1.0 and 1.1 are really strict about what will
                    // be coalesced.
                    if (segStart == segEnd) {
                        count = count + 1;
                    } else {
                        count = count + halfWarp;
                    }
                } else {
                    // 1.2 is more lenient and simply groups as
                    // necessary
                    count = count + segEnd - segStart + 1;
                }
            }
        }
    }
}


And the output:

Loads for 1234,1234 using  184,  20 stepping  176,  19
8 bytes/word; 128 segments; 16 half-warp
Best count 3180010 for 184, 20 over 1240,1236

See how the stepping here is 8 bytes in 8 because I used 8 byte ints (even
though I only need 1 bit overlap)

The total number of theeads per block would be 184*20/8 = 460.

Better Code + Numbers

From: "andrew cooke" <andrew@...>

Date: Mon, 28 Jul 2008 21:45:23 -0400 (CLT)

There were a fair number of bugs in teh code above.  Not sure I have it
right yet, but I seem to be getting numbers that make more sense.

So, the possible tactics are:

1 - Use a large integer and overlap only as little as possible.
2 - Use a small integer and overlap by a whole segment
3 - Use a large integer and overlap by a whole segment

For a "very large" (ie each dimension significantly larger than the
largest possible tile dimension) data area, searching only over the
largest tiles (ie given X, calculate Y from memory limitations etc) the
relative numbers of memory loads (smaller the better) are:

1 - 10
2 - 2
3 - 1

So it's clearly better to overlap by a whole segment, even though more
memory is "thrown away" (as expected).  The relative speeds for the two
integer sizes just reflects the sizes themselves (4 v 8 bytes).  Since
larger integers load more slowly this may not be significant.

For the original size I was using (1234 x 1234 bytes) things are less
clear because the size of the tile approaches the size of the data in some
configurations, so tweaking tiles shapes becomes significant (in fact [1]
won out because a tile could cover all the data, but [3] was still close).

Andrew

Comment on this post