Galois › Blog » 2009

Tech Talk: The Fleet Architecture

June 30th, 2009 by Levent Erkok

The July 7th Galois Tech Talk will be delivered by Ivan Sutherland, titled “The Fleet Architecture”

Date: Tuesday, July 7th, 2009
Time: 10:30am – 11:30am
Location: Galois, Inc.
421 SW 6th Ave. Suite 300
(3rd floor of the Commonwealth Building)
Portland, OR 97204

Slides are now available.

Abstract: This talk describes a radically different architecture for computing called Fleet. Fleet accepts the limitations to computing imposed by physics: moving data around inside a computer costs more energy, more delay, and more chip area than the arithmetic and logical operations ordinarily called “computing.” Fleet puts the programmer firmly in charge of the most costly resource, communication, instead of in charge of the arithmetic and logical resources that are now almost free. Fleet treats arithmetic and logical operations as side effects of where the programmer sends data.

Fleet achieves high performance through fine grain concurrency. Everything Fleet does is concurrent at the lowest level; programmers who wish sequentiality must program it explicitly. Fleet presents a stark contrast to today’s multi-core machines in which programmers seek concurrency in an inherently sequential environment.

The Fleet architecture uses a uniform switch fabric to simplify chip design. A few thousand identical copies of a programmable interface connect a thousand or so repetitions of basic arithmetic, logical, input-output, and storage units to the switch fabric. The uniform switch fabric and its identical programmable interfaces replace many of the hard parts of designing the computing elements themselves.

Both software and FPGA simulators of a Fleet system are available at UC Berkeley. Berkeley students have written a variety of Fleet programs; their work helped to define what the programmable interface between computing and communication must do. A simple compiler now produces the programs required at source and destination to provide flow-controlled communication. We expect work on a higher-level language to appear soon as a PhD dissertation.

A recent 90 nanometer TSMC test chip, called Infinity, demonstrated switch fabric performance at about 4 GHz. A new test chip, called Marina, has just gone out for fabrication. Marina will test the programmable interface, and if successful, will give us confidence to build a complete Fleet. We seek participation from sponsors, programmers, and designers of basic computation elements.

Bio: Ivan Sutherland is a Visiting Scientist at Portland State University where he and Marly Roncken have recently established the “Asynchronous Research Center” (ARC). The ARC occupies both physical and intellectual space half way between the Computer Science (CS) and Electrical and Computer Engineering (ECE) departments at the university. The ARC seeks to free designers from the tyranny of the clock by developing better tools and teaching methods for design of self-timed systems. Prior to moving to Portland, Ivan spent 25 years as a Fellow and Vice President at Sun Microsystems. A graduate of Carnegie Tech, Ivan got his PhD at MIT in 1963 and has taught at Harvard, University of Utah, and Caltech.

Dr. Sutherland received the 1988 Turing Award, for his pioneering work in the field of computer graphics.

Galois has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities. The talks are open and free. An RSVP is not required, but feel free to contact the organizer with questions and comments.

Posted in Community, Tech Talks, Technology | Comments (7)

Galois, Inc. Wins Two Small Business Research Awards from Federal Agencies

June 29th, 2009 by Galois

Galois, Inc., a Portland, Oregon research and development company, has been awarded two Phase I Small Business Innovative Research contracts. Galois will be engaging with the Department of Energy and the Department of Homeland Security on innovative technology solutions.

DHS Topic: Highly Scalable Identity Management Tools

Galois has been granted a Phase I SBIR from the Department of Homeland Security to develop a reusable identity management metasystem which will be designed foundationally to support government certification for deployment across agency boundaries, focusing on open standards, secure development, and a cross-domain design.

The Department of Homeland Security’s charter has a fundamental requirement to collaborate with other government agencies. Secure collaboration on this scale requires strong identity management which can “vouch for” DHS personnel working with other agencies and makes it possible to provide DHS resources to individuals in other agencies whose work requires it.

Anticipated Benefits: This work will provide an opportunity to deploy standard trusted components in a variety of agencies, each of which can continue to maintain its own method of managing identity and authorization. Agencies can share information based on this layer, which will evolve to support a wide variety of needs.

Potential commercial applications: Compliance with government standards of trustworthiness in software used for critical purposes, along with a user-centric approach to identity management, can enable Internet users to merge their many usernames and passwords, allow critical transactions to be executed with a higher degree of trust, and help bring about an environment where e-voting increases voters’ trust in the validity of the outcome of elections.

DOE Topic: Grid 2.0: Collaboration and Sharing on the Grid

Galois has been granted a Phase I SBIR from the Department of Energy to implement a Web 2.0 collaboration system based on Grid technologies. Galois’ system will allow dispersed scientific teams to collaborate effectively on large amounts of data produced by collections of networked computers.

Grid computing makes accessible significant computational and data resources to distributed teams of scientific researchers. In doing so, it also poses a challenge: How do distributed teams collaborate effectively with these resources?

The problem is determining how best to apply social and collaboration software techniques to improve the efficiency of collaboration between distributed teams working on grid systems.

Potential Commercial Applications: Grid computing is inherently social in the sense of involving multiple, loosely connected parties. Social collaboration in the area of large datasets is relevant to industrial and academic scientists.

About Galois, Inc.

Galois is a research and development company with a strong drive to transition technology from research into practice in the commercial and government sphere. Located in downtown Portland, Galois is a company of around 35 employees, including software developers, project managers, and business development personnel. Galois has experience in programming language design and compiler implementation, secure web application development, secure operating system development, and several other fields. Since its founding in 1999, Galois has been funded for R&D by members of the Intelligence Community and the DoD. Read more about Galois’ research and technology on their web site: www.galois.com.

Posted in Galois News, Technology | Comments (0)

Tech Talk: Verifying Stream Fusion with Isabelle/HOLCF

June 23rd, 2009 by Levent Erkok

The June 30th Galois Tech Talk will be delivered by Brian Huffman, titled “Verifying Stream Fusion with Isabelle/HOLCF”

Date: Tuesday, June 30th, 2009
Time: 10:30am – 11:30am
Location: Galois, Inc.
421 SW 6th Ave. Suite 300
(3rd floor of the Commonwealth Building)
Portland, OR 97204

Slides from the talk.

Abstract: Stream fusion is a system for removing intermediate data structures from Haskell programs that manipulate lists. Formal verification of such libraries requires very precise modeling in a theorem prover, to avoid strictness-related bugs.

In this talk I will present a formalization of the stream fusion library in Isabelle/HOLCF, a theorem proving environment designed especially for reasoning about functional programs. I will show how to prove the correctness of various stream functions using “fixed-point induction”, a powerful reasoning principle for general recursive functions.

Bio: Brian Huffman is a PhD student in Computer Science at Portland State University, working with advisor John Matthews. He studies formal reasoning with the Isabelle theorem prover, specializing in formalized mathematics and semantics of functional languages. He is currently the maintainer of Isabelle/HOLCF, a logic for domain theory.

Posted in Community, Formal Methods, Functional Programming, Haskell, Tech Talks, Technology | Comments (0)

Tech Talk: A Newbie’s Exploration of Separation Logic

June 16th, 2009 by Levent Erkok

The June 23rd Galois Tech Talk will be delivered by John Launchbury, titled “A Newbie’s Exploration of Separation Logic.”

Date: Tuesday, June 23rd, 2009
Time: 10:30am – 11:30am
Location: Galois, Inc.
421 SW 6th Ave. Suite 300
(3rd floor of the Commonwealth Building)
Portland, OR 97204

Abstract: I was just privileged to be in a Separation Logic Tutorial, given by its inventor, John Reynolds. Separation logic allows descriptions of storage and other resources concisely, providing a novel system for reasoning about imperative programs with shared mutable data structures. Recent years have seen a flurry of activity in Separation Logic, extending it to apply from shared-variable concurrency to permission based access control mechanisms. In this informal chalk-talk I will introduce the basics of Separation Logic, providing an overview of the fundamental notions of proof techniques.

Bio: John Launchbury is the CTO of Galois, Inc. Prior to founding Galois in 1999, John conducted research and instructed in Computer Science and Engineering at the Oregon Graduate Institute School of Science and Engineering at OHSU. John received First Class Honors in Mathematics from Oxford University in 1985. He holds a Ph.D. in Computing Science from University of Glasgow and won the British Computer Society’s distinguished dissertation prize.

Posted in Community, Formal Methods, Misc, Tech Talks, Technology | Comments (0)

Tech Talk: Orc in Haskell

June 9th, 2009 by Levent Erkok

The June 16th Galois Tech Talk will be delivered by Trevor Elliott, titled “Orc in Haskell.”

Date: Tuesday, June 16th, 2009
Time: 10:30am – 11:30am
Location: Galois, Inc.
421 SW 6th Ave. Suite 300
(3rd floor of the Commonwealth Building)
Portland, OR 97204

Abstract: Concurrency is difficult to realize successfully. The Orc language tackles this problem by introducing explicit concurrency as part of its core. It presents a clean, and somewhat monadic, style of programming that should look familiar to Haskell users. I will give a quick introduction to the Orc language, using several examples to motivate its use. Following this introduction, a monadic Haskell embedding of the major features will be presented, bringing a type system to Orc.

Bio: Trevor Elliott is a member of the technical staff at Galois, Inc. His interests center around functional programming, and the effective use of type systems.

Slides are available for download.

Update: the source is now available on Hackage (though changed from the version presented at this talk).

Posted in Community, Functional Programming, Haskell, Misc, Tech Talks | Comments (7)

Tech Talk: A Taste of DDT

June 1st, 2009 by Levent Erkok

The June 9th Galois Tech Talk will be delivered by Jim Grundy titled “A Taste of DDT.”

Date: Tuesday, June 9th, 2009
Time: 10:30am – 12:00 noon
Location: Galois, Inc.
421 SW 6th Ave. Suite 300
(3rd floor of the Commonwealth Building)
Portland, OR 97204

Abstract: DDT is a partial implementation of the directed testing approach to test generation. The presentation will likely interest you if you are interested in how directed testing works, or what it is like to use in practice.

This seminar presents a rational reconstruction of an experience of using DDT to test a rather rich FIFO/list module implemented in C. The module in question is about 1500 lines of code with a dozen or so entry points. The presentation walks through the user experience of writing and running a first naïve test harness for the module, finding and correcting issues in the code, up to a final declaration of victory.

The presentation is rather long, about 1.5 hours, but takes the form of a gently paced walk through a user experience, and as such is rather less taxing on the concentration that you might expect for a talk of its duration.

Bio: Jim Grundy is a research scientist with Intel Corporation. His interests include functional programming, mechanized and interactive reasoning and their application to establishing the correctness of hardware and software systems.

Posted in Misc | Comments (3)