skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Dynamical Behavior of a Colony Migration System: Do Colony Size and Quorum Threshold Affect Collective Decision?
Award ID(s):
2052820 1716802
PAR ID:
10469184
Author(s) / Creator(s):
; ; ;
Publisher / Repository:
SIAM
Date Published:
Journal Name:
SIAM Journal on Applied Mathematics
ISSN:
0036-1399
Page Range / eLocation ID:
S43 to S64
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Bacteria often attach to surfaces and grow densely-packed communities called biofilms. As biofilms grow, they expand across the surface, increasing their surface area and access to nutrients. Thus, the overall growth rate of a biofilm is directly dependent on its “range expansion” rate. One factor that limits the range expansion rate is vertical growth; at the biofilm edge there is a direct trade-off between horizontal and vertical growth—the more a biofilm grows up, the less it can grow out. Thus, the balance of horizontal and vertical growth impacts the range expansion rate and, crucially, the overall biofilm growth rate. However, the biophysical connection between horizontal and vertical growth remains poorly understood, due in large part to difficulty in resolving biofilm shape with sufficient spatial and temporal resolution from small length scales to macroscopic sizes. Here, we experimentally show that the horizontal expansion rate of bacterial colonies is controlled by the contact angle at the biofilm edge. Using white light interferometry, we measure the three-dimensional surface morphology of growing colonies, and find that small colonies are surprisingly well-described as spherical caps. At later times, nutrient diffusion and uptake prevent the tall colony center from growing exponentially. However, the colony edge always has a region short enough to grow exponentially; the size and shape of this region, characterized by its contact angle, along with cellular doubling time, determines the range expansion rate. We found that the geometry of the exponentially growing biofilm edge is well-described as a spherical-cap-napkin-ring, i.e., a spherical cap with a cylindrical hole in its center (where the biofilm is too tall to grow exponentially). We derive an exact expression for the spherical-cap-napkin-ring-based range expansion rate; further, to first order, the expansion rate only depends on the colony contact angle, the thickness of the exponentially growing region, and the cellular doubling time. We experimentally validate both of these expressions. In line with our theoretical predictions, we find that biofilms with long cellular doubling times and small contact angles do in fact grow faster than biofilms with short cellular doubling times and large contact angles. Accordingly, sensitivity analysis shows that biofilm growth rates are more sensitive to their contact angles than to their cellular growth rates. Thus, to understand the fitness of a growing biofilm, one must account for its shape, not just its cellular doubling time. 
    more » « less
  2. This paper describes a new approach to register-pressure-aware instruction scheduling, using Ant Colony Optimization (ACO) . ACO is a nature-inspired optimization technique that researchers have successfully applied to NP-hard sequencing problems like the Traveling Salesman Problem (TSP) and its derivatives. In this work, we describe an ACO algorithm for solving the long-standing compiler optimization problem of balancing Instruction-Level Parallelism (ILP) and Register Pressure (RP) in pre-allocation instruction scheduling. Three different cost functions are studied for estimating RP during instruction scheduling. The proposed ACO algorithm is implemented in the LLVM open-source compiler, and its performance is evaluated experimentally on three different machines with three different instruction-set architectures: Intel x86, ARM, and AMD GPU. The proposed ACO algorithm is compared to an exact Branch-and-Bound (B&B) algorithm proposed in previous work. On x86 and ARM, both algorithms are evaluated relative to LLVM's generic scheduler, while on the AMD GPU, the algorithms are evaluated relative to AMD's production scheduler. The experimental results show that using SPECrate 2017 Floating Point, the proposed algorithm gives geometric-mean improvements of 1.13% and 1.25% in execution speed on x86 and ARM, respectively, relative to the LLVM scheduler. Using PlaidML on an AMD GPU, it gives a geometric-mean improvement of 7.14% in execution speed relative to the AMD scheduler. The proposed ACO algorithm gives approximately the same execution-time results as the B&B algorithm, with each algorithm outperforming the other on a substantial number of hard scheduling regions. ACO gives better results than B&B on many large instances that B&B times out on. Both ACO and B&B outperform the LLVM algorithm on the CPU and the AMD algorithm on the GPU. 
    more » « less