|High Performance Dynamic Arrays
Most real-world applications use data structures which grow dynamically at runtime. These programs use the dynamic array (vector) implementation available in most programming languages, for example, STL with C++. These libraries handle dynamic growth of data and allow data to be accessed in O(1) time, using arrays. However, in existing implementations of multidimensional dynamic arrays, rows are allocated non-contiguously on the heap, so that each row could grow dynamically. This array of arrays implementation needs multiple memory accesses to read a single data location. We implement a high performance dynamic array (VARRAY) using contiguous multidimensional arrays, so that each location can be accessed via a single memory read. VARRAY improves TLB and cache reuse and other compiler optimizations such as tiling. VARRAY also results in efficient generation of data communication code for distributed memory. Preliminary results using this new data structure show speedup of 12% for 2d arrays and 17% for 3d arrays for programs in polybench.
Using array implementation of dynamic arrays, also exposes parallelization opportunity, whose data layout changes dynamically at runtime. Using array notation, we transform PUSH/POP operations on dynamic arrays as read/write operations on array to detect the dependencies in program. We assume non-affine access and runtime dependent control flow, to model irregular parallelism. We then parallelize the data structure operations At runtime we use 2 techniques to paralleize a sequence iterations on dynamic array
These techniques can remove the inherent dependencies on PUSH-POP operations and improve the program performance.
Designing ICT systems for rural users in the developing world can be very hard. Just a few of the challenges we face are low literacy, limited experience using digital technologies, and the wide variability in spoken languages. To overcome some of these issues, we created VideoKheti, a mobile system that uses speech, graphics, and touch interaction to help low-literate farmers in rural India find and watch agricultural extension videos in their own language and dialect.
|Distributed Systems Research@PLATO
Kapil Vaswani, Researcher, Microsoft Research India, talks about the PLATO group's research in distributed Systems.
|Accelerated Learning with Kernels
Kernel learning algorithms occupy a prominent position within machine learning having given state-of-the-art performance in several domains. Much of the power of kernel methods comes from their ability to implicitly represent complex functions in high dimensional spaces. This however, comes at a price of increased hypothesis complexity that causes these algorithms to be slow at prediction time. With an increase in demand for real time applications, this prevents kernel algorithms from being applied to several domains. A second limitation of traditional kernel-based learning methods is their dependence on so-called 'Mercer kernels' that prevents them from fully utilizing rich domain-specific knowledge in the learning process.
Our work seeks to address both these issues by developing kernel learning algorithms that offer fast prediction routines. We further develop a learning framework that allows efficient use of non-Mercer kernels in addition to offering fast training and testing routines.
|From Computing Research to Surprising Inventions
|Over and Out: Augmented Reality and the Future of User Interfaces
|How to Design Simple and Efficient Mechanisms that are also Composable
|Engaging Practitioners in Software Engineering Research
|Microsoft Research and the Evolution of Computing
|TypeRighting: CHI 2013 Promo
A 30 second introduction to our CHI 2013 note on TypeRighting
- Microsoft Research India
196/36 2nd Main
Sadashivnagar, Bangalore 560 080