


Bryan He
$10,000 Scholarship Recipient
Age: 18 Buffalo, NY Category: Technology Project Title: “A Simple Optimal Binary Representation of Mosaic Floorplans and Baxter Permutations.” 


Bryan's research project is about finding a binary representation (also called binary code) for "mosaic floorplans". A mosaic floorplan is a rectangle R divided into n smaller rectangles (called blocks) by horizontal and vertical line segments. Floorplanning is the first stage in the design of VLSI (Very Larrge Scale Integration) circuits: R represents a chip area and the blocks represent circuit components. A floorplan describes the placement of components. In later design stages, chip designers need to solve various optimization problems (such as area minimization and wire length minimization). The optimization algorithms need a short binary code to generate and enumerate mosaic floorplans. The shorter the code, the more efficient these algorithms will be. Thus finding short binary codes is an important research area and has applications in VLSI optimization algorithms.
Bryan designed an optimal binary representation of mosaic floorplans. Mosaic floorplans are used in the process of creating chip layout designs during verylargescale integration (VLSI). Previously, the shortest binary representation of an nblock mosaic floorplans used 4nbits, but using Bryan's representation, only (3n3)bits are needed. It has been proven that this length is asymptotically optimal for representing mosaic floorplans. Other representations of mosaic floorplans already existed, but used more bits than necessary, so he wanted to figure out which parts of the representation were redundant. Eventually, he was able to reduce the length of the representation, but it was still above the optimal representation length. Finally, after considering the representation carefully, Bryan was able to reduce the length to the optimal length. A more compact coding of mosaic floorplans allows more efficient floorplan algorithms to be created. Mosaic floorplans have been shown to have a bijection with Baxter permutations, so Bryan's method can also be used to create an optimal representation of Baxter permutations.
Bryan was a finalist at Intel Science Talent Search and is interested in machine learning, artificial intelligence and robotics. In the future he plans to pursue a doctorate in Computer Science, and hopes to continue doing research in computer science. He is a freshman studying Computer Science at the California Institute of Technology.
Photos: Click the links below to view hires photos of Bryan: 

NEXT >
Click here to view the full listing of the 2012 Davidson Fellows.
Click here to view Bryan's press release.
For all media inquiries, please contact DavidsonFellowsMedia@davidsongifted.org.