A long time in the making, we finally launched the new website for SCALGO a few days ago. The new website has product descriptions and lots of easy to read information about our technology and I hope that it can inspire LIDAR users to get more out of their huge LIDAR datasets. After all, it is a shame to spend millions in flight time and equipment and then not use the point cloud optimally because the data is too big to handle.
One of the things I like about our new site is our mapping example which is built on top of Google Maps using our own custom server for our data. Unfortunately we don’t have the rights to show some of the very detailed LIDAR-derived models we have worked with. However, we have also played with the full SRTM model, and we show two different examples online. In the first you can play with global flood maps by controlling the sea-level and discover what parts of the world gets flooded. Unlike most other similar computations available online, this is not done by simply intersection the raster with a horizontal plane at the water level and marking everything underneath this plane as flooded – doing so would ignore the effect of many features in the terrain (e.g. dikes). Additionally, the computation is done so that we can show arbitrary sea-levels, and not just levels in increments of e.g. 10cm. In the other computation you can play with flow accumulation, where water falls on the terrain and runs downstream, forming rivers and smaller tributaries. Note that the resolution of the SRTM model is relatively coarse so dikes and other small natural barriers are not always reflected as they are missing in the data. You can read more about these computations here. The computations were performed using our newly released SCALGO Hydrology and SCALGO Simplify packages.
Floating Point Puzzle of the Day (C++)
Here a small puzzle for those of you who have nothing better to do:
Let “x” be a float.
Can the following assert fire? (assert is the standard macro from cassert).
{ float y=x; assert(x==y); }
If yes, how?
If no, why not?
Danish Meatballs (Frikadeller)
I’ve made Danish Meatballs (also known as “Frikadeller”) a couple of times since I moved to North Carolina, and I have recived a couple of requests for the recipe. I figured I’d put it up here to help spread the gospel of “fine” Danish cuisine in America. This recipe is based on the recipe found here (in Danish).
Ingredients
Metric Imperial Item
500g 1.1lb Ground Pork
1.5tsp 1.5tsp Coarse Salt
80g 0.64 cup Wheat Flour
1 1 Egg
200g 0.44 lb (~1 onion) Yellow Onion
1.5dl 5 fl. oz Skim Milk
0.25 tsp 0.25 tsp Pepper
Step-by-step Instructions
- Mix the pork with the salt and let it sit for a couple of minutes. This will improve the meat’s ability to absorb the milk.
- Grate the onion.
- Mix all the ingredients and stir thoroughly. Hold back some of the milk and flour, this can be used to tweak the consistency of the mix. If you use fatty or recently defrosted meat you should probably use a little less milk.
- Heat a skillet over medium heat, and use plenty of oil or butter. Use a teaspoon or a tablespoon (depending on the size you want) to form the meatballs in the palm of your hand, and put them on the pan in a circular pattern (so you can remember which order you put them down). They will need a few minutes on each side, depending on their size.
Suresh is calling for people to commit to a new discussion site for theoretical computer scientists. Sounds like fun!
From MADALGO comes word of a summer school on geometric data structures, looks like fun!
Here is the official announcement:
MADALGO Summer School on GEOMETRIC DATA STRUCTURES
August 16-19, 2010, Aarhus, Denmark
www.madalgo.au.dk/datastructures2010
OVERVIEW AND GOAL
Geometric data structures are methods of efficiently storing and querying data in two or more dimensions. Working with geometric data often requires the use of specialized and fundamentally geometric techniques. The goal of the summer school is to provide an in-depth introduction to some of the key techniques in geometric data structures, while highlighting a number of open problems.
LECTURES
The school will be taught by experts in the area of geometric data structures:
- Timothy Chan (University of Waterloo)
- Sariel Har-Paled (University of Illinois at Urbana-Champaign)
- John Iacono (Polytechnic Institute of New York University)
- Mihai Patrascu (AT&T)
PARTICIPATION
The summer school will take place on August 16-19, 2010 at Center for Massive Data Algorithmics (MADALGO) in the Department of Computer Science, University of Aarhus, Denmark.
The school is targeted at graduate students, as well as researchers interested in an in-depth introduction to geometric data structures.
The capacity of the summer school is limited. Prospective participants should register using the online registration form available at www.madalgo.au.dk/datastructures2010 as soon as possible. Registering graduate students must also have their supervisor send a letter confirming their graduate student status directly to madalgo@madalgo.au.dk; the subject line of the email should be ‘student_last_name/SS_2010/confirming’. Registration is on a first-come-first-serve basis and will close on July 1, 2010.
Registration is free; handouts, coffee breaks, lunches and a dinner will be provided by MADALGO and the Aarhus University.
ORGANIZING COMMITTEE
- Lars Arge (MADALGO)
- Gerth S. Brodal (MADALGO)
- John Iacono (Polytechnic Institute of New York University)
- Else Magård (MADALGO)
- Sara Ølholm (Aarhus University)
ABOUT MADALGO
Center for MAssive Data ALGOrithmics is a major basic research center funded by the Danish National Research Foundation. The center is located at the Department of Computer Science, University of Aarhus, Denmark, but also includes researchers at CSAIL, Massachusetts Institute of Technology in the US, and at the Max Planck Institute for Informatics and at Frankfurt University in Germany. The center covers all areas of the design, analysis and implementation of algorithms and data structures for processing massive data (interpreted broadly to cover computations where data is large compared to the computational resources), but with a main focus on I/O-efficient, cache-oblivious and data stream algorithms.
Via Lars Arge, information about an interesting post doc opportunity at MADALGO:
An interdisciplinary Post Doc position is available at Aarhus
University, Denmark, starting August 2010 or later. The responsibilities
of the Post Doc will include work on geospatial problems on the boundary
between computer science and biology, more specifically between
algorithms and ecology/biodiversity. Modest teaching responsibilities
may also be required. The Post Doc will be affiliated with the Danish
National Research Foundation Center MADALGO (Center for Massive Data
Algorithmics – www.madalgo.au.dk) under the supervision of computer
science Professor Lars Arge (person.au.dk/en/large@cs), but will also
work extensively with researchers in the Ecoinfomatics & Biodiversity
group at the Department of Biological Sciences under the supervision of
Professor Jens-Christian Svenning (person.au.dk/en/svenning@biology).
The Post Doc should focus on problems in relation to computationally
efficient use of modern detailed (and thus massive) topographic data in
various global-change-relevant modeling applications. These problems
include the computation of fine-resolution topography-derived variables
on a global scale, as well as local- and global-scale flooding scenario
modeling and impact assessment.
Applications are welcomed from computer science researchers with clearly
demonstrated skills in the design, analysis and implementation of
algorithms (preferably also with I/O-efficient algorithms), as well as
from geoinformatics or biology researchers with clearly demonstrated
skills in ecoinformatics, GIS, and programming. Researchers with
interdisciplinary research experience will be preferred. Applicants
should apply by uploading a letter of interest and a CV, as well as
indicate at least two names of references for recommendations, using the
application form available at www.madalgo.au.dk. To be assured of full
consideration, applications must arrive by May 17, 2010. Applications
will be considered until the position is filled.
For further information contact Professor Lars Arge at
large@madalgo.au.dk or Professor Jens-Christian Svenning at
svenning@biology.au.dk.
Tethering lets you to use the 3G connection on your Android-based cell phone to browse the internet from your laptop. Some phones come with tethering applications build int, but on other phones tethering is not possible – or you have to jump through a lot of hoops to enable it.
The nice new Motorola DROID phone does not have a tethering ability by standard (all-though a Verizon representative told that Verizon will be coming out with something at some point) but it is still possible to tether it using the Proxoid application. Unlike other approaches, you do not have to root your phone.
A detailed installation guide is available here. To use this guide with the Motorola DROID phone you should put the following line in /etc/udev/rules.d/11-android.rules:
SUBSYSTEMS=="usb", SYSFS{idVendor}=="22b8", SYSFS{idProduct}=="41db", MODE="0666", OWNER="USERNAME"
If you’re on Ubuntu Karmic Koala 9.10 you should restart udev using the following command:
sudo service udev restart
When trying to connect to the android phone you mave have to run
sudo ./adb kill-server
sudo ./adb start-server
Before you can see the device (this happens if the server was already started when you changed the udev rules). This works on Ubuntu Karmic Koala.
Be aware that tethering may not be allowed by your service provider, you should read your contract to find out.
NVIDIA’s currently released version of CUDA does not directly with Ubuntu 9.10 which uses GCC 4.4 as the default compiler. However, it is quite easy to make it work and the following guide goes through the entire installation process in some detail.
I use the 64bit version of CUDA, go here to get it:
http://www.nvidia.com/object/cuda_get.html
(I selected Linux 64 bit and Ubuntu 9.04 .)
This lets you download the CUDA Drivers, the CUDA Toolkit and the CUDA SDK, and you will end up with three files:
cudadriver_2.3_linux_64_190.18.run
cudatoolkit_2.3_linux_64_ubuntu9.04.run
cudasdk_2.3_linux.run
Installing the NVIDIA driver:
Cuda needs at least version 190 of the linux driver
1.
Uninstall existing NVIDIA drivers and nvidia-glx. (Use gui or aptitude).
2.
Install driver:
Quit x (log out of your desktop, go to a virtual terminal (CTRL+ALT+F1), login, run
$ sudo service gdm stop
3.
Run
$ sudo cudadriver_2.3_linux_64_190.18.run
to install the driver, follow the prompts.
Say yes to install 32 bit compatibility libraries.
If you want you can let the installer overwrite the Xorg configuration file.
4.
Reboot and log back in.
5.
Run
$ nvidia-settings
to verify that your driver version is at least 190.18. Look for the driver version in the window:
Installing the CUDA Toolkit:
After having installed the driver we now need to install the CUDA toolkit itself.
1.
Run:
$ sudo sh cudatoolkit_2.3_linux_64_ubuntu9.04.run
2.
Press enter to install at the
/usr/local/cuda
default location.
3.
Register the new library files, run:
$ sudo gedit /etc/ld.so.conf.d/cuda.conf
and add
/usr/local/cuda/lib64
to the otherwise empty file and save it. Then run:
$ sudo ldconfig
You can also add
export PATH=/usr/local/cuda/bin:$PATH
export LD_LIBRARY_PATH=/usr/local/cuda/lib64:$LD_LIBRARY_PATH
to the end of your ~/.bashrc file.
(You should then login and out again of start a new bash with
bash --
to update your environment.
Installing the CUDA SDK and Compiling the Example Programs
We will now install the CUDA SDK to your own home directory so you can play with the supplied demos:
1.
Run:
$ sh cudasdk_2.3_linux.run
I chose to install it at the default location.
2.
As CUDA does not yet work with GCC 4.4 you will have to install gcc-4.3:
$ sudo aptitude install gcc-4.3 g++-4.3
3.
Go to SDK source dir:
cd ~/NVIDIA_GPU_Computing_SDK/C$
4.
Create a directory and create symlinks to gcc-4.3/g++-4.3
$ mkdir mygcc
$ cd mygcc
$ ln -s $(which g++-4.3) g++
$ ln -s $(which gcc-4.3) gcc
$ cd ..
5.
Edit common makefile:
$ gedit common/common.mk
Find the lines that specify CC, CXX and LINK and change them to:
CXX := g++-4.3
CC := gcc-4.3
LINK := g++-4.3 -fPIC
Add
#use gcc-4.3
NVCCFLAGS+=--compiler-bindir=${HOME}/NVIDIA_GPU_Computing_SDK/C/mygcc
Before the line that says “ifeq ($(nvcc_warn_verbose),1)”. This tells the nvcc computer that it should look in mygcc for gcc, which will cause it to pickup our gcc-4.3 compiler.
6.
You should now be able to compile everything by running
$ make
This should now compile all the examples in the SDK without errors.
Verify Installation
We can now verify that everything is working:
1.
Run:
$ bin/linux/release/deviceQuery
On my machine I get the following output (depending on your harware, you ourput may be different):
CUDA Device Query (Runtime API) version (CUDART static linking)
There is 1 device supporting CUDA
Device 0: "GeForce 8800 Ultra" CUDA Driver Version: 2.30 CUDA Runtime Version: 2.30 CUDA Capability Major revision number: 1 CUDA Capability Minor revision number: 0 Total amount of global memory: 804585472 bytes Number of multiprocessors: 16 Number of cores: 128 Total amount of constant memory: 65536 bytes Total amount of shared memory per block: 16384 bytes Total number of registers available per block: 8192 Warp size: 32 Maximum number of threads per block: 512 Maximum sizes of each dimension of a block: 512 x 512 x 64 Maximum sizes of each dimension of a grid: 65535 x 65535 x 1 Maximum memory pitch: 262144 bytes Texture alignment: 256 bytes Clock rate: 1.51 GHz Concurrent copy and execution: No Run time limit on kernels: Yes Integrated: No Support host page-locked memory mapping: No Compute mode: Default (multiple host threads can use this device simultaneously)
Test PASSED
Press ENTER to exit...
You should now be good to go. Here’s an screenshot of the volumeRender demo:
$ bin/linux/release/volumeRender
Remember to use gcc-4.3/g++-4.3 and the –compiler-bindir option to nvcc when compiling your own CUDA source.
PostDoc’ing at Duke
Today I’m starting my new job as a Postdoctoral Associate at Duke University where I’ll be working with Pankaj Agarwal. I am now trying to find a car (anyone here selling a car in the Raleigh/Durham area?).
ISAAC 2009 Accepted Papers
The list of accepted papers for ISAAC 2009 in Hawaii has now been posted.
I’m happy to see that my paper “Counting in the Presence of Memory Faults” is on the list (number 136), it has been co-authored by Gerth Brodal, Allan Jørgensen and Gabriel Moruz. The paper presents counting algorithms designed in the Faulty Memory RAM proposed by Finocchi and Italiano.
A fault-tolerant resilient counting algorithm as defined in our paper is a datastructure with an increment operation and a query operation. The query algorithm returns the number of increments operations that has been performed on the data structure, within an additive error factor.
It is simple to design such a datastructure in the standard RAM using a simple integer variable, but this is not possible in faulty memory RAM where arbritrary memory cells can get corrupted at any point in time. In the paper we present tradeoff lower bounds and upper bounds and tradeoffs between the additive error factor and the time used per operation.



