W B Langdon Non-GP 2011 Abstracts

W.B.Langdon . 19 April 2012 2011 papers , full list

Formal Concept Analysis on Graphics Hardware

W. B. Langdon, Shin Yoo, Mark Harman, pp413-416, CLA 2011, Amedeo Napoli and Vilem Vychodil Eds. 17-20 October, Nancy, France. (PDF). poster


We document a parallel non-recursive beam search GPGPU FCA CbO like algorithm written in nVidia CUDA C and test it on software module dependency graphs. Despite removing repeated calculations and optimising data structures and kernels, we do not yet see major speed ups. Instead GeForce 295 GTX and Tesla C2050 report 141072 concepts (maximal rectangles, clusters) in about one second. Future improvements in graphics hardware may make GPU implementations of Galois lattices competitive.

Keywords: FCA, GPU, GPGPU, CUDA C, SBSE, software module clustering, MDG, close-by-one, artificial intelligence, arithmetic intensity

Non-Recursive Beam Search on GPU for Formal Concept Analysis

W. B. Langdon and Shin Yoo and Mark Harman Technical Report RN/11/18.

Other UCL CS technical reports

In Silico Infection of the Human Genome

W. B. Langdon and M. J. Arno, In EvoBIO 2012, Mario Giacobini and Leonardo Vanneschi and William Bush Eds., LNCS 7246, pp245-249, 11-13 April, Malaga, Spain. DOI PDF slides See journal article.

More Mouldy Data: Virtual Infection of the Human Genome

Jumping the silicon barrier

W. B. Langdon and M. J. Arno, Technical Report RN/11/14.

Genes find a way
Mendel's discovery of the essential digital nature of inheritance. Barbara McClintock's discovery of Transposons in Maize whereby genes move not only from parent to child but also along chromosomes. Micrograph of genetic transfer along a pilus linking two bacteria. (1959 Akiba and Ochia discovered the first interspecies gene transfer.) 2011 Mycoplasma bacteria genes are transfered between computers, including into the reference human genome DNA sequence held by GenBank and into Affymetrix GeneChips.


The human genome sequence database contains DNA sequences very like those of mycoplasma bacteria. It appears they infect not only molecular Biology laboratories but were picked up by experimenters from contaminated samples and inserted into GenBank as if they were human. At least one mouldy EST (Expressed Sequence Tag) has transferred from public databases to commercial tools (Affymetrix HG-U133 plus 2.0 microarrays, probeset 1570561_at). We report a second example (DA466599) and suggest there is a need to clean up genomic databases but fear current tools will be inadequate to catch genes which have jumped the silicon barrier.

arXiv:1106.4192 More Mouldy Data: Another mycoplasma gene jumps the silicon barrier into the human genome.

Keywords: Human Microbiome, Horizontal gene transfer HGT, human-associated bacteria.

Comments: data directory contains results of AF241217 and DA466599 blast runs by EBI in Cambridge
[q-bio.GN] suplementary data directory (poster).
blog slashdot blogspot
Amara D. Angelica. Der Spiegel, Verseuchte Datenbanken, 04.07.2011 page 120. Genbanken von Bakterien infiziert science.orf.at, 28.06.2011. Mouldy chips New Scientist, 60 Seconds, 13 July 2011

Other UCL CS technical reports

Debugging CUDA

W. B. Langdon Presented at CIGPU 2011, pp415-422. (PDF DOI slides).


During six months of intensive nVidia CUDA programming of an artificial intelligence (AI) application many bugs were created. We seek to pass on the software engineering lessons learnt, particularly those relevant to parallel general-purpose computation on graphics hardware GPGPU.

A reviewer said:
Summary : GPU via CUDA programming is tricky and there are many "gotchas". This paper aims to pass on some experience of developing with CUDA to those who are experimenting with more-advanced projects.

Performing with CUDA

W. B. Langdon Presented at CIGPU 2011, pp423-430. (PDF DOI slides).


Recently a GPGPU computation intelligence application had to be redesigned to overcome performance problems. A number of software engineering lessons were learnt from this and other projects. We describe those about obtaining high performance from nVidia GPUs and practical aspects of CUDA C software development.