Chulalongkorn University Theses and Dissertations (Chula ETD)

Parallelizing stochastic L-systems simulation of plant stem and branch growth

Other Title (Parallel Title in Other Language of ETD)

การจำลอง L-systems แบบเฟ้นสุ่มชนิดขนานของการเติบโตของลำต้นและกิ่งต้นไม้

Year (A.D.)

2002

Document Type

Thesis

First Advisor

Chidchanok Lursinsap

Second Advisor

Suchada Siripant

Faculty/College

Faculty of Science (คณะวิทยาศาสตร์)

Degree Name

Master of Science

Degree Level

Master's Degree

Degree Discipline

Computational Science

DOI

10.58837/CHULA.THE.2002.1103

Abstract

Lindenmayer system or L-system has been recognized for a long time as a mathematical theory of plant development. The principle of system is based on a rewriting language in which each part of plant is produced by substituting along with production rules. Since substituting on each part of the plant can be performed simultaneously and independenty without interfering to each other parts it is clearly seen that the whole job can be separated and performed by group of computers. In this research a parallel algorithm for stochastic L-system has been developed and examined. The program was implemented in C programming and Message-Passing Interface package to enable the system running on virtual parallel machines. The result was investigated for feasibility to improve operating time of stochastic L-system. The speedup factor is poor for lower derivation length, but it become pretty good at derivation length greater than 7. Maximum value of speedup factor for this research is approximately 19.6 at derivation length of 9 with 9 processes operated simultaneously.

Other Abstract (Other language abstract of ETD)

ระบบวิธีของ Lindenmayer หรือ L-system นั้นเป็นที่รู้จักกันมานานแล้วในฐานะทฤษฎีทางคณิตศาสตร์ ที่ใช้ในการอธิบายรูปแบบการเจริญเติบโตของต้นไม้ต่างๆ โดยหลักการสำคัญของระบบวิธีนี้ก็คือการสร้างส่วนต่างๆ ของต้นไม้ ด้วยการนำชิ้นส่วนใหม่เข้าแทนที่ชิ้นส่วนเดิมตามกฎเกณฑ์ที่ได้กำหนดไว้ และเนื่องจากการแทนที่ชิ้นส่วนนี้สามารถทำได้โดยลำพังและไม่กระทบถึงส่วน อื่นๆ ของต้นไม้นั้น จึงเห็นได้ว่า อาจจะนำงานทั้งหมดมาแบ่งออกเป็นส่วนย่อยๆ แล้วส่งให้เครื่องคอมพิวเตอร์หลายๆ เครื่องจัดการพร้อมๆ กันได้ โดยใช้อัลกอริทึมในการประมวลผลแบบขนาน ซึ่งโปรแกรมที่ใช้ในงานวิจัยครั้งนี้เขียนขึ้นด้วยภาษาซี ประกอบกับชุดโปรแกรม Message-Passing Interface ซึ่งช่วยให้กลุ่มเครื่องคอมพิวเตอร์สามารถทำงานได้แบบขนาน และจากการวิเคราะห์หาความเป็นไปได้ในการเพิ่มประสิทธิภาพการทำงานของ Stochastic L-system นี้ปรากฏว่า ค่า speedup factor มีค่าค่อนข้างต่ำเมื่อจำนวนรอบในการแทนค่าน้อย แต่เมื่อจำนวนรอบในการแทนค่ามากกว่า 7 พบว่า speedup factor นั้นกลับมีค่าที่น่าพอใจ โดยค่าสูงสุดของ speedup factor ในงานวิจัยครั้งนี้มีค่าประมาณ 19.6 เมื่อจำนวนรอบในการแทนค่าเท่ากับ 9 และใช้การประมวลผล 9 กระบวนพร้อมกัน

Link to Full Text

Share

COinS