Class Presentations - CSCE 622

Class Presentations - CSCE 622.md

• HotDrink and Graph visualizations
  • Using hotdrink and building an adapter for it to work with D3.
  • D3 works on HTML5 and SVGs, making it work with mobile as well.
  • Observables on both sides (Hotdrink and D3) and glue-code between them.
  • Examples of Dijkstra's algorithm, Knight's tour and Elastic Triangle expressed in a constraint system.
  • Github repo: TBD
  • We saw programs which take an entire constraint system as a parameter, and the generic algorithm it's running is that of the user interface.
• A mobile web-crawler
  • Use of the webview is rather common in Android applications.
  • Android has a lot of malware.
  • Existing vulnerabilities in webviews allow some arbitrary code execution.
  • Need a tool to find malicious web servers targeting mobile devices: a crawler for the mobile-web.
  • Used a custom user agent for obvious reasons.
  • Used the Boost Graph Library to deal with the webgraph generated.
  • Crawled at 3.66 MB/s, stored graph in GraphML format, a total size of 1.3G.
  • OOM issues.
  • Initially saved URLs, status code and file-path in BGL itself. {I think it makes more sense to separate it out and make a separate adjacency list, and other associative data structures}
  • Improved to store hashes and not the entire URL and file path. {Used a custom hash function, difficult to evaluate optimality}
  • The graph is still in memory and needs to be written to disk.
  • Future work: analysis of JS and finding malicious code.
  • Suggestions: Use bitvectors instead of booleans, prefix trees instead of hashtables. {reversed URLs as well possibly}.
• Generic Matrix Multiplication Framework in STAPL
  • Fine-grained SUMMA implementation. {SUMMA: Scalable Universal Matrix Multiplication Algorithm}
  • Shared-object programming model {can run in distributed/shared memory}
  • Provides generic containers and algorithmic skeletons. {express the smallest unit of computation and repeat it}
  • ARMI runtime hides machine details and hides communication details.
  • Algorthms and skeleton framework in STAPL modified.
  • Repeated operations, and a sink skeleton to extract the value out.
  • Generic way of fitting the skeleton using decltype and finding-by-tag.
  • 25x speedup without optimization, just by naive parallelization.
  • Coarser tasks would make it faster. Coarser being dealing with them in sub-blocks than assigning random processors to each tiny task. This leads to better locality and hence speedup.
  • It is sequential at the lowest block level, and hence, it runs the generic matrix-mul algorithm. {BLAS would make performance better}
  • Notes: nice example of something written in terms of algorithmic skeletons.
• GAZE: A game development framework for perfect-information games.
  • Perfect information is when each player is perfectly informed of all relevant information to decide upon the next move.
  • These games are typically modeled as a decision tree {later pruned using alpha-beta}.
  • Each game position has a position value determined by heuristics.
  • The framework manages the game-tree internally and provide the necessary iterators. Alpha-beta pruning is implemented on top of this.
  • Game Tree and Game Vertex are containers being used; there are Game Traits to explain how interactions can be done.
  • Internally seems to use BGL.
  • Vertices are added to the game-tree when required. Vertex iterator is a forward iterator. Traits class to abstract away some details.
  • Sets aside some traits that the game state needs to adhere to, and the user of the library writes a game state that adheres to the concept.
  • A-B pruning is an extension of minimax algorithm, used to decrease the number of nodes.
  • The framework performs the entire process of exploring nodes and neighbors and so on.
  • {Could use more detail on what part is generic and what is not}